Lorintz Alexandru (Alex_tz307) Cerința
În urma petrecerii de ziua lui RAU-Gigel, copiii au primit atâtea bomboane încât au câștigat o energie debordantă – așa că l-au provocat pe RAU-Gigel la un concurs de … numărat!
Acestora li se dă o matrice cu N linii și M coloane, în care fiecare element este un număr natural nenul. Obiectivul lor este să determine câte submatrice (sub-dreptunghiuri formate din linii și coloane contigue) conțin exact K valori distincte.
Date de intrare
Fișierul matriceinteresanta.in conține pe prima linie trei numere N, M, respectiv K, având semnificația din enunț, iar pe următoarele N linii câte M numere separate prin câte un spațiu reprezentând elementele matricei.
Date de ieșire
Fișierul matriceinteresanta.out va conține pe prima linie un singur număr natural, reprezentând numărul de submatrice din matricea dată care conțin exact K valori distincte.
Restricții și precizări
1 ≤ N, M ≤ 3001 ≤ K ≤ 50- Elementele din matrice sunt numere naturale nenule cu valoarea cuprinsă între
1și50 - Pentru teste în valoare de
30de puncte,1 ≤ N, M ≤ 20 - Pentru alte teste în valoare de
20de puncte,1 ≤ N, M ≤ 40 - Pentru alte teste în valoare de
15de puncte,1 ≤ N, M ≤ 100 - Pentru alte teste în valoare de
10de puncte,1 ≤ N, M ≤ 200 - Pentru restul testelor se păstrează restricțiile inițiale din enunț
Exemplul 1:
Intrare
3 3 3 1 2 3 4 5 6 7 8 9
Ieșire
6
Explicație
Submatricele căutate trebuie să aibă exact 3 elemente distincte, deci singurele potrivite din exemplu sunt cele de dimensiune 1x3 sau 3x1, adică liniile și coloanele din matricea inițială, în total fiind 6.
Exemplul 2:
Intrare
3 3 3 1 1 2 3 4 1 2 2 3
Ieșire
7
Explicație
Un exemplu de submatrice care conține exact 3 numere distincte este cea de dimensiune 2x2 din colțul stânga-jos, care conține elementele 3, 4, 2, 2 (cele 3 numere distincte fiind în acest caz 2, 3 și 4), iar exemple de submatrice care nu conțin exact 3 numere sunt cea formată din totalitatea primelor 2 linii (conține 4 numere distincte) sau cea formată doar din ultima linie (conține 2 numere distincte).