== include(page="template/taskheader" task_id="sahara") ==
Poveste şi cerinţă...
Undeva, în deşertul Sahara, ilustrul biolog Sahraa Gaea a conceput şi construit un sistem de irigaţii ingenios, sistem cu care îşi propune să irige o zonă deşertică dreptunghiulară bogată în nutrienţi minerali. Zona deşertică este împărţită în $N × M$ pătrate de latură unitate. În fiecare pătrat se află un dispozitiv de picurare ce asigură o anumită cantitate de apă în funcţie de comanda primită de la centrul de control al sistemului.
Sistemul de irigare este astfel conceput încât să irige (ude), pe baza unor comenzi automatizate, parcele dreptunghiulare ale regiunii deşertice.
Orice parcelă are laturile paralele cu laturile zonei deşertice şi este identificată prin coordonatele colţurilor stânga-sus $(x1,y1)$, respectiv dreapta-jos $(x2,y2)$. La fiecare comandă se specifică parcela care va fi udată şi cantitatea de apă (exprimată în litri) cu care va fi irigat fiecare pătrat al acesteia.
Un pătrat al zonei deşertice devine fertil dacă acumulează cel puţin $Q$ litri de apă.
h2. Cerinţă
Să se determine aria maximă a unei suprafeţe conexe fertile. Prin aria unei suprafeţe înţelegem numărul de pătrate ce compun suprafaţa. Orice două pătrate fertile care au o latură comună fac parte din aceeaşi suprafaţă conexă fertilă.
h2. Date de intrare
Fişierul de intrare $sahara.in$ ...
Fişierul de intrare $sahara.in$ conţine pe prima linie trei numere naturale $N$ $M$ $Q$ despărţite prin câte un spaţiu, cu semnificaţia din enunţ.
Pe cea de-a doua linie a fişierului se găseşte un număr natural $T$. Pe fiecare dintre următoarele $T$ linii se află descrierea parcelelor udate sub forma: $x1 y1 x2 y2 q$, adică cinci numere naturale despărţite prin spaţiu, unde $x1 y1 x2 y2$ reprezintă coordonatele colţurilor stânga-sus, respectiv dreapta-jos ale parcelei, $q$ cantitatea de apă cu care va fi irigat fiecare pătrat al parcelei.
h2. Date de ieşire
În fişierul de ieşire $sahara.out$ ...
Fişierul de ieşire $sahara.out$ va conţine o singură valoare ce reprezintă aria maximă a unei suprafeţe conexe fertile.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N, M ≤ 1000$
* $1 ≤ x1 ≤ x2 ≤ N, 1 ≤ y1 ≤ y2 ≤ M$
* $1 ≤ q ≤ 1000$
* $1 ≤ Q ≤ 10000$
* $1 ≤ T ≤ 50000$
* Iniţial zona deşertică nu conţine ”apă”
* Pot exista suprafaţe conexe fertile formate dintr-un singur pătrat fertil
* Parcelele se pot suprapune
h2. Exemplu
table(example). |_. sahara.in |_. sahara.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 8 7 5
7
1 1 3 6 1
4 2 5 7 2
2 3 4 7 3
1 2 4 3 3
5 1 6 3 4
5 5 7 6 2
6 4 8 7 3
| 10
|
h3. Explicaţie
...
Cantitatea de apă acumulată în solul regiunii este:
$1 4 4 1 1 1 0$
$1 4 7 4 4 4 3$
$1 4 7 4 4 4 3$
$0 5 8 5 5 5 5$
$4 6 6 2 4 4 2$
$4 4 4 3 5 5 3$
$0 0 0 3 5 5 3$
$0 0 0 3 3 3 3$
Aria maximă a unei suprafeţe fertile este egală cu $10$. Suprafaţa se consideră fertilă dacă acumulează cel puţin $5$ litri de apă.
== include(page="template/taskfooter" task_id="sahara") ==
