| Fişierul intrare/ieşire: | sahara.in, sahara.out | Sursă | Lot Sovata 2014 - Baraj 1 Juniori |
| Autor | Eugen Nodea | Adăugată de |  Alexandru Valeanu •AlexandruValeanu |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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ă.
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ă.
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 ×2 y2 q, adică cinci numere naturale despărţite prin spaţiu, unde x1 y1 ×2 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.
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.
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
Exemplu
| 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 |
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ă.
