Fişierul intrare/ieşire:	omogene.in, omogene.out	Sursă	ONI 2016, clasa a 9-a
Autor	Dan Pracsiu	Adăugată de	Alexandru Valeanu •AlexandruValeanu
Timp execuţie pe test	0.65 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Omogene

Se consideră o matrice cu L linii şi C coloane care memorează doar valori din mulţimea {0,1,2}. O submatrice nevidă (formată din cel puţin o linie şi cel puţin o coloană) a acestei matrice o numim omogenă dacă numărul valorilor de 0 este egal cu numărul de valori de 1 şi egal cu numărul valorilor de 2.
De exemplu, în matricea
0 1 2 0
1 2 0 1
sunt şase submatrice omogene, acestea fiind:
0 1 2 | 1 2 0 | 0 1 2 | 1 2 0 | 1 2 0 | 2 0 1
1 2 0 | 2 0 1 |

Submatricele a treia şi a patra sunt formate din prima linie a matricei iniţială, iar submatricele a cincea şi a şasea sunt formate din a doua linie.

Cerinţă

Să se determine câte submatrice nevide omogene există.

Date de intrare

Fişierul omogene.in conţine pe prima linie numerele naturale L şi C. Pe următoarele L linii se află câte C numere naturale separate prin spaţii reprezentând câte o linie din matrice.

Date de ieşire

Fişierul omogene.out va conţine pe prima linie un singur număr natural reprezentând numărul submatricelor nevide omogene.

Restricţii

• 2 ≤ L ≤ C ≤ 5.000
• 4 ≤ L * C ≤ 65.536
• Atenţie, o submatrice este formată dintr-o secvenţă continuă de linii şi coloane, deci, de exemplu, dacă se aleg dintro matrice liniile 1, 2 şi 5, atunci acestea nu formează o submatrice.
• Numărul submatricelor omogene va fi mai mic decât 2*10⁹.
• Întreaga matrice poate fi submatrice omogenă.

Exemplu

Cum se trimit solutii?