Planificación óptima (2) P96822


Statement
 

pdf   zip

thehtml

Se tiene n tareas a realizar, cada una de las cuales requiere un cierto número de minutos ‍ti. Para cada tarea i, se conoce el minuto máximo fi en el cual i debe estar finalizada. Además, realizar cada tarea i tiene valor vi. Si sólo se dispone del intervalo de tiempo desde el instante 0 hasta el minuto m, ¿cuál es el máximo valor total de las tareas que se pueden realizar respetando las restricciones?

Entrada

La entrada consiste en diversos casos. Cada caso empieza con n y m, seguidas de n triplas con ti, fi y vi. Podéis suponer 1 ≤ n ≤ 100, m ≥ 1, 1 ≤ tifi y vi ≥ 1.

Salida

Para cada caso, escribid la máxima suma de valores de tareas realizables.

Puntuación

  • test-1:  ‍ Entradas donde m ≤ 100, ti = 1, fi ≤ 100 y vi = 1.  ‍10 Puntos ‍
  • test-2:  ‍ Entradas donde m ≤ 108, ti = 1, fi ≤ 106 y vi ≤ 106.  ‍25 Puntos ‍
  • test-3:  ‍ Entradas donde m ≤ 108, fi ≤ 106 y vi = 1.  ‍25 Puntos ‍
  • test-4:  ‍ Entradas donde m ≤ 108, fi ≤ 106 y vi ≤ 106.  ‍40 Puntos ‍
Public test cases
  • Input

    4 4
    1 4 1
    1 3 1
    1 2 1
    1 1 1
    
    3 2
    1 3 1
    1 3 1
    1 3 1
    

    Output

    4
    2
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Official solutions
    C++
    User solutions