== include(page="template/taskheader" task_id="mm") ==
Poveste si cerinta...
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: $l{~sus~}(i), c{~stanga~}(i), l{~jos~}(i), c{~dreapta~}(i)$ si $cost(i)$. Zona dreptunghiulara $i$ acopera toate celulele matricii aflate la coordonate $(linie, coloana)$, pentru care $l{~sus~}(i)≤linie≤l{~jos~}(i)$ si $c{~stanga~}(i)≤coloana≤c{~dreapta~}(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.
h2. Date de intrare
Fisierul de intrare $mm.in$ ...
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: $l{~sus~}(i), c{~stanga~}(i), l{~jos~}(i), c{~dreapta~}(i)$ si $cost(i)$
h2. Date de iesire
In fisierul de iesire $mm.out$ ...
In fisierul de iesire $mm.out$ veti afisa un singur numar, reprezentand costul minim al amplasarii patratului in interiorul matricii.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 250.000$
* $1 ≤ L ≤ N$
* $1 ≤ P ≤ 100.000$
* $1 ≤ l{~sus~}(i) ≤ l{~jos~}(i) ≤ N$
* $1 ≤ c{~stanga~}(i) ≤ c{~dreapta~}(i) ≤ N$
* $1 ≤ cost(i) ≤ 2.000.000.000$
h2. Exemplu
table(example). |_. mm.in |_. mm.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|10 5 3
2 2 7 7 10
6 7 9 7 20
3 4 6 10 13
|13
|
h3. 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$.
== include(page="template/taskfooter" task_id="mm") ==
