Fişierul intrare/ieşire:ssk.in, ssk.outSursăONI 2015 baraj gimnaziu
AutorDana LicaAdăugată decella.florescuCella Florescu cella.florescu
Timp execuţie pe test1.2 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Ssk (baraj gimnaziu)

Manole a învăţat de la profesorul de informatică cum să calculeze suma elementelor oricărei matrice A cu N linii şi M coloane. El numerotează liniile de la 1 la N şi coloanele de la 1 la M. Mai mult, Manole fiind extrem de pasionat de numere, va calcula sumele tuturor subtablourilor din cadrul matricei A. Şirul acestor sume îl scrie pe o hârtie, după ce l-a ordonat crescător. Prin subtablou el înţelege o zonă dreptunghiulară din matricea A, identificată prin colţul stânga-sus (x1, y1) şi colţul dreapta-jos (x2, y2), elementele subtabloului fiind toate elementele A[i][j] pentru care x1 ≤ i ≤ x2 şi y1 ≤ j ≤ y2. Suma unui subtablou este suma tuturor elementelor sale.

Cerinţă

Scrieţi un program care, cunoscând valorile elementelor matricei A, determină al K-lea termen din şirul ordonat al sumelor tuturor subtablourilor matricii A.

Date de intrare

Fişierul de intrare ssk.in conţine pe prima linie numerele naturale N M K separate prin câte un spaţiu, având semnificaţia din enunţ. Pe următoarele N linii se află câte M numere naturale separate prin spaţii, reprezentând elementele matricei A.

Date de ieşire

Fişierul de ieşire ssk.out va conţine o singură linie pe care va fi scris un număr natural reprezentând răspunsul la cerinţă.

Restricţii

  • 1 ≤ N ≤ 150
  • 1 ≤ M ≤ 150
  • 1 ≤ K ≤ numărul de termeni din şirul ordonat
  • 0 ≤ A[i][j] ≤ 1000 unde 1 ≤ i ≤ N şi 1 ≤ j ≤ M
  • Numerotarea termenilor din şirul ordonat al sumelor tuturor subtablourilor se va face începând de la 1

Exemplu

ssk.inssk.out
2 3 14
3 2 7
4 1 0
9

Explicaţie

Şirul ordonat al tuturor sumelor subtablourilor matricei este:
0 1 1 2 3 3 4 5 5 5 7 7 7 9 10 10 12 17
A patrusprezecea sumă este 9.

Trebuie sa te autentifici pentru a trimite solutii. Click aici