Fişierul intrare/ieşire:stalpi.in, stalpi.outSursăpreONI 2008, Runda 4
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.4 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Stalpi

O anumita strada din Orasul Efemer poate fi privita ca axa Ox a numerelor naturale. De-a lungul acestei strazi se afla N stalpi de iluminare publica. Al i-lea stalp se afla la coordonata Xi si pentru o suma de Ci lei se poate amplasa un bec in interiorul stalpului, care va lumina Si metri in stanga stalpului si Di metri in dreapta stalpului. Primarul orasului vrea ca toti stalpii sa fie vizibili. Un stalp este vizibil daca in interiorul lui este amplasat un bec sau daca se afla in raza de iluminare a altui stalp in care s-a amplasat un bec. El s-a decis sa aleaga o multime de stalpi si sa instaleze cate un bec in fiecare dintre acestia. Problema este ca va trebui sa plateasca pentru fiecare stalp ales costul necesar amplasarii unui bec in stalpul respectiv si vrea ca suma acestor costuri sa fie minima. Ajutati primarul afland costul minim necesar pentru ca toti stalpii din Orasul Efemer sa fie vizibili.

Date de intrare

Fisierul de intrare stalpi.in contine pe prima linie numarul N avand semnificatia din enunt. Pe urmatoarele N linii urmeaza cate un cvadruplu X C S D cu semnificatia ca stalpul i (pe linia i+1 exista informatii despre stalpul i) se afla la coordonata X, costul pentru a amplasa un bec in interiorul lui este C si daca se realizeaza acest lucru va lumina S metri in stanga si D metri in dreapta.

Date de iesire

Pe prima linie a fisierului de iesire stalpi.out se afla un numar natural MIN reprezentand costul minim necesar pentru ca toti stalpii din oras sa fie vizibili.

Restrictii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ Xi, Si, Di ≤ 109
  • 1 ≤ Ci ≤ 100 000
  • Daca se amplaseaza un bec in stalpul i el va lumina orice stalp j cu proprietatea Xi-Si≤ Xj ≤ Xi+Di
  • Nu exista doi stalpi diferiti care sa aibe aceiasi coordonata X
  • Toate numerele din fisierul de intrare sunt naturale
  • In cel putin 40% din teste 1 ≤ N ≤ 1000
  • Datorita infrastructurii ciudate a stalpilor un bec poate fi amplasat in interiorul acestora

Exemplu

stalpi.instalpi.out
4
3 1 3 5
1 10 10 9
7 2 5 3
10 18 4 4
3

Explicatie

Se va amplasa un bec in interiorul stalpilor 1 si 3. Stalpul 2 va fi luminat de stalpul 1 iar stalpul 4 va fi luminat de stalpul 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content