Rezolvare PBinfo #1461

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 teste 4 ≤ N, M ≤ 300 și 1 ≤ 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