| Fişierul intrare/ieşire: | mm.in, mm.out | Sursă | Selectie echipe ACM ICPC, UPB 2008 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 2.5 sec | Limită de memorie | 128000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Mm
Se considera o matrice N x N (cu N linii si N coloane, numerotate de la 1 la N). In interiorul acestei matrice exista P zone dreptunghiulare. Pentru fiecare astfel de zona i (1≤i≤P) se cunosc urmatorii 5 parametrii: lsus(i), cstanga(i), ljos(i), cdreapta(i) si cost(i). Zona dreptunghiulara i acopera toate celulele matricii aflate la coordonate (linie, coloana), pentru care lsus(i)≤linie≤ljos(i) si cstanga(i)≤coloana≤cdreapta(i). cost(i) reprezinta costul zonei dreptunghiulare i.
Se doreste amplasarea unui patrat de latura L strict in interiorul matricii date. Un patrat de latura L ocupa o zona din interiorul matricii avand L linii si L coloane. Costul amplasarii patratului este egal cu maximul costurilor zonelor dreptunghiulare pe care acesta le intersecteaza (daca nu intersecteaza nicio zona, costul sau este 0). Determinati costul minim al amplasarii unui patrat de latura data L strict in interiorul matricii.
Date de intrare
Fisierul de intrare mm.in contine pe prima linie 3 numere intregi, separate prin cate un spatiu: N, L si P. Urmatoarele P linii descriu cate o zona dreptunghiulara. A i-a dintre aceste linii contine 5 numere intregi, separate prin cate un spatiu: lsus(i), cstanga(i), ljos(i), cdreapta(i) si cost(i)
Date de iesire
In fisierul de iesire mm.out veti afisa un singur numar, reprezentand costul minim al amplasarii patratului in interiorul matricii.
Restrictii
- 1 ≤ N ≤ 250.000
- 1 ≤ L ≤ N
- 1 ≤ P ≤ 100.000
- 1 ≤ lsus(i) ≤ ljos(i) ≤ N
- 1 ≤ cstanga(i) ≤ cdreapta(i) ≤ N
- 1 ≤ cost(i) ≤ 2.000.000.000
Exemplu
| mm.in | mm.out |
|---|---|
| 10 5 3 2 2 7 7 10 6 7 9 7 20 3 4 6 10 13 | 13 |
Explicatie
Patratul poate fi amplasat cu coltul stanga-sus la celula (1,1). Astfel, el intersecteaza zonele dreptunghiulare 1 si 3, costul sau fiind max(10,13)=13.
