| Fişierul intrare/ieşire: | gardieni.in, gardieni.out | Sursă | preONI 2008 Runda 3 |
| Autor | Filip Cristian Buruiana | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Gardieni
Seful unei companii de pe o planeta necunoscuta doreste ca sediul firmei sa fie pazit in fiecare moment intreg de timp de la 1 la T. El a primit N oferte de la firme de securitate de tipul a b c, avand semnificatia ca pentru pretul de c unitati poate fi angajat un paznic care sa pazeasca compania o unitate de timp, dar doar intr-un moment de timp t cuprins in intervalul inchis [a,b] (a ≤ t ≤ b). Pe planeta unde se afla compania tehnologia nu este foarte avansata si de aceea este nevoie de ajutorul vostru pentru a afla costul minim care ar trebui sa il plateasca seful companiei astfel incat compania sa fie pazita in fiecare moment intreg de timp de la 1 la T. Bineinteles, pot fi angajati mai multi paznici de la aceiasi firma de securitate iar fiecare paznic angajat pazeste compania exact o singura unitate de timp.
Date de intrare
Fisierul de intrare gardieni.in contine pe prima linie doua numere naturale N si T avand semnificatia din enunt. Urmeaza apoi N linii care contin cate trei numere naturale a b c reprezentand ofertele fiecarei firme de securitate.
Date de iesire
In fisierul de iesire gardieni.out se afla pe prima linie numarl natural MIN, reprezentand costul minim care trebuie platit astfel incat compania sa fie pazita in fiecare moment intreg de timp de la 1 la T.
Restrictii
- 1 ≤ N ≤ 50 005
- 1 ≤ T ≤ 1 000 000
- 1 ≤ a ≤ b ≤ T
- 1 ≤ c ≤ 220
- Oricum am alege 11 oferte ale firmelor de securitate si considerand intervalele asociate lor [a1,b1], [a2,b2] ... [a11,b11] nu exista un numar natural x astfel incat a1 ≤ x ≤ b1, a2 ≤ x ≤ b2 ..., a11 ≤ x ≤ b11.
- Sa garanteaza ca in fiecare moment de timp exista cel putin un paznic care poate fi angajat
Exemplu
| gardieni.in | gardieni.out |
|---|---|
| 3 5 2 4 3 1 3 1 5 5 2 | 8 |
Explicatie
Pentru momentele de timp 1, 2 si 3 se va angaja cate un paznic de la a doua firma si se va plati in total 1+1+1=3. Pentru momentul 4 se va alege un paznic de la prima firma pentru costul de 3 unitati iar in momentul 5 se va alege un paznic de la a treia firma pentru costul de 2 unitati. Costul total va fi 1+1+1+3+2=8.
