Fişierul intrare/ieşire:mm.in, mm.outSursăSelectie echipe ACM ICPC, UPB 2008
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test2.5 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/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.inmm.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content