== include(page="template/taskheader" task_id="sahara") ==
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ă.
Poveste şi cerinţă...
h2. Date de intrare
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.
Fişierul de intrare $sahara.in$ ...
h2. Date de ieşire
Fişierul de ieşire $sahara.out$ va conţine o singură valoare ce reprezintă aria maximă a unei suprafeţe conexe fertile.
În fişierul de ieşire $sahara.out$ ...
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 |
| 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
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
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") ==
