Fişierul intrare/ieşire:	matrice.in, matrice.out	Sursă	ONI 2007, clasa 10
Autor	Mircea Bogdan Pasoi	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Matrice

Se considera o matrice binara B (cu valori 0 sau 1) cu N linii si M coloane, liniile si coloanele fiind numerotate de la 1 la N, respectiv de la 1 la M. Matricea B este generata dupa regula B_i,j = R_i xor C_j, unde R si C sunt vectori binari de lungime N, respectiv M. Numim dreptunghi de colturi (x₁,y₁) (x₂,y₂) cu x₁ ≤ x₂ si y₁ ≤ y₂, multimea elementelor B_i,j cu x₁ ≤ i ≤ x₂ si y₁ ≤ j ≤ y₂. Aria unui astfel de dreptunghi este (x₂-x₁+1)*(y₂-y₁+1).

Cerinta

Determinati numarul maxim de elemente egale cu 0 intr-un dreptunghi a carui arie este exact A, precum si numarul de dreptunghiuri pentru care se obtine acest numar maxim.

Date de intrare

Fisierul de intrare matrice.in contine pe prima linie numerele naturale N, M, A separate prin cate un spatiu. A doua linie va contine N valori 0 sau 1 separate prin cate un spatiu, reprezentand elementele vectorului R, iar a treia linie va contine M valori 0 sau 1 separate prin cate un spatiu, reprezentand elementele vectorului C.

Date de iesire

Fisierul de iesire matrice.out va contine o singura linie pe care vor fi scrise doua numere naturale separate printr-un singur spatiu Zmax Nsol, reprezentand in ordine numarul maxim de elemente egale cu 0 intr-un dreptunghi a carui arie este exact A, precum si numarul de dreptunghiuri pentru care se obtine acest numar maxim.

Restrictii

• 1 ≤ N,M ≤ 30 000
• 1 ≤ A ≤ 5 000 000
• Pentru 40% din teste N,M ≤ 300
• Prin x xor y se intelege operatia sau exclusiv, mai exact:

Exemplu

Explicatie

Matricea B:

Numarul maxim de valori 0 dintr-un dreptunghi de arie 4 este 2.
Cele 5 dreptunghiuri de arie 4 cu numar maxim de 0 sunt:

• (1,1)(1,4)
• (2,1)(2,4)
• (1,1)(2,2)
• (1,2)(2,3)
• (1,3)(2,4)

Cum se trimit solutii?