Fișierul intrare/ieșire	joc6.in, joc6.out	Sursă	ONI 2011 baraj gimnaziu
Autor	Silviu Candale	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	1.8 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Joc6 (baraj gimnaziu)

Pentru desfășurarea jocului se utilizează k seturi de câte n+2 bile. Dintre cele n+2 bile:

• n sunt inscripționate cu numerele distincte de la 1 la n, reprezentând valoarea fiecărei bile;
• două bile sunt inscripționate cu numărul 0, au un rol special și nu au valoare.

La joc participă k jucători, numerotați cu numerele distincte de la 1 la k. Jocul se desfășoară astfel:

• din primul set de bile, primul jucător primește p bile pe care trebuie să le aranjeze, în linie, astfel încât numerele inscripționate pe aceste bile să formeze o secvență de valori consecutive și de sumă maximă;
• din al doilea set de bile, al doilea jucător primește p bile pe care trebuie să le aranjeze, în linie, astfel încât numerele inscripționate pe aceste bile să formeze o secvență de valori consecutive și de sumă maximă;
• ...
• din al k-lea set de bile, al k-lea jucător primește p bile pe care trebuie să le aranjeze, în linie, astfel încât numerele inscripționate pe aceste bile să formeze o secvență de valori consecutive și de sumă maximă;
• o secvență poate conține bile cu valoarea 0 ce pot înlocui orice valoare nenulă, fără a modifica suma valorilor din secvență.

Câștigă jucătorul care obține secvența cu suma valorilor bilelor maximă, aceasta numindu-se suma câștigătoare.

Cerință

Scrieți un program care să citească numărul n, numărul k, valorile bilelor primite de fiecare jucător, și care să determine numărul câștigătorul jocului, precum și valoarea sumei câștigătoare.

Date de intrare

Prima linie a fișierului de intrare joc6.in conține trei numere, n k p, separate prin câte un spațiu, cu semnificația din enunț. Fiecare din următoarele k linii (în ordinea crescătoare a numerelor jucătorilor) conține câte p numere naturale, separate prin câte un spațiu, reprezentând valorile bilelor primite de fiecare jucător.

Date de ieșire

În fișierul de ieșire joc6.out se vor scrie două numere naturale, separate printr-un un spațiu. Prima valoare reprezintă numărul câștigătorului jocului. A doua valoare reprezintă suma câștigătoare.

Restricții

• 1 ≤ n ≤ 500000
• 1 ≤ k ≤ 20
• 1 ≤ p ≤ min(100000,n+2)
• Se garantează că fiecare jucător primește bile cu valori distincte, cu excepția bilelor speciale.
• Dacă suma câștigătoare este obținută de mai mulți jucători, jucătorul câștigător va fi jucătorul cu numărul cel mai mic.

Exemplu