Fişierul intrare/ieşire:gardieni.in, gardieni.outSursăpreONI 2008 Runda 3
AutorFilip Cristian BuruianaAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.ingardieni.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content