Din cauza blestemelor dușmanilor, asupra plantației de ‘noledge a vrăjitorului Arpsod s-a năpustit o ploaie de…meteoriți. Plantația vrăjitorului e foarte bine delimitată: aceasta are forma unei matrice cu N
linii și M
coloane, iar în fiecare celulă era plantat câte un fir de ‘noledge. Din motive clare de răzbunare, dușmanii nu s-au mulțumit cu o singură ploaie, astfel, pe plantația vrăjitorului au căzut meteoriți în mai multe reprize. La fiecare repriză, pe fiecare celulă a unui dreptunghi bine delimitat, au căzut exact C
meteoriți. După ce ploaia s-a oprit, pe fiecare celulă se afla un “bloc” de piatră de înălțime egală cu numărul meteoriților căzuți în acea celulă. Arpsod, foarte furios, a luat următoarea decizie: va construi un laborator exact peste meteoriții căzuți, de unde își va pedepsi dușmanii. El a hotărât că cel mai bun amplasament pentru acest laborator este la înălțime maximă. Totodată, el își dorește ca laboratorul lui să aibă o suprafață cât mai mare.
Cerința
Deoarece Arpsod şi arhitectul său, Ierdnac, sunt prea ocupaţi să pregătească schița viitorului laborator, vă roagă pe voi să determinați aria maximă a unei suprafețe cu celule învecinate, de înălțime maximă precum și numărul de fire de ‘noledge rămase neatinse după căderea meteoriților ( poate au ratat vreunu’ ! ).
Date de intrare
Pe prima linie a fișierului meteoriti.in
se află trei numere naturale separate prin spațiu: N
și M
, reprezentând dimensiunile plantației și R
, reprezentând numărul de reprize de meteoriți. Pe următoarele R
linii se vor afla cinci valori separate prin spațiu: r1 c1 r2 c2 C
, unde r1 c1
reprezintă coordonatele colțului stânga sus ( linie coloană ) iar r2 c2
coordonatele colțului dreapta jos ( linie coloană ) ale dreptiunghiului pe care vor cădea meteoriți iar C
reprezintă numărul de meteoriți ce vor cădea pe fiecare celulă din cele delimitate.
Date de ieșire
În fișierul meteoriti.out
se va scrie, pe o singură linie, separate prin spațiu, aria maximă a unei suprafețe de înălțime maximă, formată numai din celule vecine respectiv numărul de fire de ‘noledge neafectate de meteoriți.
Restricții și precizări
4 ≤ N, M ≤ 2.000
1 ≤ R ≤ 100.000
1 ≤ r1 ≤ r2 ≤ N
1 ≤ c1 ≤ c2 ≤ M
1 ≤ C ≤ 20.000
- Două celule se consideră vecine dacă au cel puțin o latură comună.
- Înălțimea inițială a celulelor se consideră
0
. - Se garantează că pentru
30%
din teste4 ≤ N, M ≤ 300
și1 ≤ R ≤ 300
- Pentru rezolvarea corectă a primei cerinţe se acordă
80%
din punctajul pe testul respectiv iar pentru rezolvarea corectă a celei de-a doua cerinţe se acordă20%
din punctajul pe testul respectiv - Fișierul de ieșire TREBUIE să conțină exact DOUĂ valori chiar dacă doriți să rezolvați o singură cerință din cele două
- Dacă îi veți da răspunsul corect vrăjitorului, acesta vă va primi și pe voi prin laboratorul său.
- NU este bine să îl supărați pe vrăjitor!
Exemplu:
meteoriti.in
5 6 7 2 2 4 3 1 4 4 4 6 2 1 5 4 6 1 2 5 3 6 1 2 3 4 3 1 5 1 5 3 3 4 2 4 2 1
meteoriti.out
3 12
Explicație
Matricea după meteoriţi:
0 0 0 0 1 1
0 1 2 0 2 2
0 1 2 0 2 2
0 2 2 2 3 3
3 3 3 0 0 0
Înălțimea maximă este 3 iar aria maximă a unei suprafețe de înălțime 3
este tot 3