Fişierul intrare/ieşire:sahara.in, sahara.outSursăLot Sovata 2014 - Baraj 1 Juniori
AutorEugen NodeaAdăugată deAlexandruValeanuAlexandru Valeanu AlexandruValeanu
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.insahara.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ă. 

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?