Buffet libre P28082


Statement
 

pdf   zip

thehtml

Considerad un restaurante de buffet libre con una sola hilera de n platos. Cada plato i aporta ci calorías. Además, tiene asignado un número xi, de manera que si se coge ese plato, no se puede coger ninguno de los siguientes xi platos ni a su derecha ni a su izquierda. Conociendo los valores ci y xi de cada plato, ¿podéis calcular el número máximo de calorías que se pueden ingerir?

Entrada

La entrada consiste en varios casos. Cada caso empieza con una n entre 1 y 1000. Siguen n ‍pares de naturales ci xi, con 1 ≤ ci ≤ 106 y xi < n.

Salida

Para cada caso, escribid el número máximo de calorías que se pueden ingerir.

Puntuación

  • Test-1:  ‍ Entradas con n ≤ 8.  ‍17 Puntos ‍
  • Test-2:  ‍ Entradas con n ≤ 60.  ‍25 Puntos ‍
  • Test-3:  ‍ Entradas de todo tipo.  ‍58 Puntos ‍
Public test cases
  • Input

    3
    2 1
    5 1
    2 0
    
    4
    8 2
    5 1
    10 0
    8 2
    

    Output

    5
    16
    
  • Information
    Author
    Albert Martínez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++