Fişierul intrare/ieşire:demolish.in, demolish.outSursăinfo-arena 1.0
AutorFilip Cristian BuruianaAdăugată de
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Demolish

Patratel a strans profit serios din afacerile cu struti si acum doreste sa se extinda. Cu banii pe care ii are intentioneaza sa isi construiasca o ferma in regiune. Regiunea este de forma dreptunghiulara si are M kilometri lungime si N kilometri latime, iar ferma trebuie sa fie si ea dreptunghiulara si sa aiba laturile paralele cu ale regiunii. In regiune sunt insa construite alte F ferme ale unor oameni la fel de bogati ca si Patratel, ferme tot dreptunghiulare si tot cu laturile paralele cu ale regiunii. Patratel este om pretentios ( ca si strutii sai, de altfel ), si doreste o ferma de DX kilometri lungime si DY kilometri latime. Constructia unei astfel de ferme nu este intotdeauna posibila pentru ca depinde de asezarea celorlalte F ferme. Fiecare ferma are un cost de demolare ( costul pe care Patratel trebuie sa il plateasca sa demoleze ferma respectiva ). El doreste sa isi plaseze ferma proprie in regiune astfel incat suma costurilor de demolare ale fermelor intersectate de ferma sa fie minima.
Doua ferme se intersecteaza daca si numai daca un punct de pe laturile primei ferme se gaseste strict in interiorul celei de a doua ferme ( adica ele nu se intersecteaza daca se ating doar laturile ).

Cerinta

Sa se determina costul minim pe care il plateste Patratel pentru a-si construi ferma.

Date de Intrare

Prima linie a fisierului demolish.in contine cinci numere naturale M, N, F, DX si DY ( in aceasta ordine ), cu semnificatia din enunt. Fiecare din urmatoarele F linii contine tot cate cinci numere, (x1 y1 ×2 y2 C), unde (x1 y1) reprezinta coordonatele coltului stanga-jos ale unei ferme din regiune, (x2 y2) coordonatele dreapta-sus ale aceleiasi ferme, iar C costul de demolare al fermei respective. Pentru un astfel de set avem intotdeauna 0 ≤ x1 < x2 ≤ M, 0 ≤ y1 < y2 ≤ N si 0 ≤ C ≤ 200 000.

Date de Iesire

Prima linie a fisierului demolish.out contine COST, costul minim cerut. A doua linie contine patru numere intregi separate de cate un spatiu, (x1 y1 ×2 y2), reprezentand pozitionarea fermei in regiune: (x1 y1) - coordonatele coltului stanga-jos si (x2 y2) - coordonatele dreapta-sus a fermei construite de Patratel pentru a obtine costul minim COST. Daca sunt mai multe posibilitati de amplasare, se va afisa cea care are x1 minim, iar daca si in acest caz sunt mai multe posibilitati, se va afisa cea care are y1 minim.

Restrictii si precizari

  • 4 < M, N < 500 001
  • 0 < DX < M + 1, 0 < DY < N + 1
  • F < 30 001
  • Evident, fermele deja construite in regiune nu se intersecteaza
  • Oricare doua ferme nu se intersecteaza daca se ating doar laturile
  • Pot exista doua ferme din cele F care au acelasi cost de demolare

Exemplu

demolish.indemolish.out
12 10 6 7 8
2 3 5 8 3
5 7 7 9 7
8 4 12 8 22
7 1 9 2 4
0 0 1 2 10
1 9 2 10 6
14
1 0 8 8

Explicatie

Costul minim se obtine daca ferma este dispusa conform coordonatelor (1 0 8 8), intersectand fermele 1, 2 si 4, care trebuiesc demolate. Suma costurilor tuturor demolarilor efectuate este de 3+7+4 = 14. O alta plasare posibila care duce tot la costul 14 este (1 1 8 9), dar aceasta nu duce la indeplinirea conditiei de minimalitate a coordonatelor.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content