Fişierul intrare/ieşire:matrice.in, matrice.outSursăONI 2007, clasa 10
AutorMircea Bogdan PasoiAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 Bi,j = Ri xor Cj, unde R si C sunt vectori binari de lungime N, respectiv M. Numim dreptunghi de colturi (x1,y1) (x2,y2) cu x1 ≤ x2 si y1 ≤ y2, multimea elementelor Bi,j cu x1 ≤ i ≤ x2 si y1 ≤ j ≤ y2. Aria unui astfel de dreptunghi este (x2-x1+1)*(y2-y1+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:
x xor y1
1
11

Exemplu

matrice.inmatrice.out
2 4 4
0 1
1 0 0 1
2 5

Explicatie

Matricea B:

11
11

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)
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content