Fişierul intrare/ieşire:gard.in, gard.outSursăONI 2002
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.025 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Gard

O echipa de K muncitori a fost angajata sa vopseasca un gard format din N scanduri numerotate de la 1 la N, de la stanga spre dreapta. Fiecare muncitor i (1 ≤ i ≤ K) se aseaza in fata scandurii Si si poate vopsi numai un interval compact (adica numerele de ordine ale scandurilor din interval sunt consecutive) avand maxim Li scanduri, interval care trebuie sa contina scandura Si. Pentru fiecare scandura vopsita, acesta este platit cu suma Pi. Din motive de eficienta, oricare 2 muncitori din echipa trebuie sa vopseasca intervale de scanduri disjuncte (adica oricare scandura a gardului poate fi vopsita de cel mult un membru al echipei).
Fiind conducatorul echipei de muncitori, dumneavoastra doriti sa determinati pentru fiecare membru al echipei intervalul de scanduri pe care acesta va trebui sa il vopseasca, astfel incat castigul total sa fie maxim. Castigul total este egal cu suma castigurilor realizate de fiecare membru al echipei. Castigul realizat de fiecare muncitor este egal cu numarul de scanduri vopsite de acesta inmultit cu Pi (pentru muncitorul cu numarul i).

Cerinta

Scrieti un program care determina castigul maxim obtinut de cei K muncitori.

Date de Intrare

Fisierul de intrare gard.in contine:

gard.inSemnificatie
N K
L1 P1 S1
L2 P2 S2
...
LK PK SK
N - numarul de scanduri; K - numarul de muncitori
Li - numarul maxim de scanduri ce pot fi vopsite de muncitorul cu numarul i
Pi - suma primita de muncitorul i pentru fiecare scandura vopsita de acesta
Si - scandura din gard in fata careia se aseaza muncitorul i

Date de Iesire

In fisierul gard.out veti afisa castigul maxim obtinut de intreaga echipa de muncitori.

Restrictii si precizari

  • 1 ≤ N ≤ 16.000
  • 1 ≤ K ≤ 100
  • 1 ≤ Pi ≤ 10.000
  • 1 ≤ Li,Si ≤ N
  • Toate numerele Si vor fi distincte.
  • Nu trebuie vopsite neaparat toate cele N scanduri ale gardului.
  • Este permis ca unul sau mai multi dintre membrii echipei sa nu vopseasca nici o scandura, caz in care scandura in fata careia s-au asezat initial poate fi vopsita, eventual, de catre alt muncitor.

Exemplu

gard.ingard.out
8 4
3 2 2
3 2 3
3 3 5
1 1 7
17

Explicatie

Muncitorul 1 vopseste intervalul de scanduri [1, 2]; muncitorul 2 vopseste intervalul de scanduri [3, 4]; muncitorul 3 vopseste intervalul de scanduri [5, 7]; muncitorul 4 nu vopseste nici o scandura.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content