Protegiendo las minas
Al jugar videojuegos, la gestión de recursos es fundamental.
Hay
n minas de oro ubicadas en diferentes coordenadas . Cada una de estas minas puede producir una cierta cantidad de oro . Sin embargo, protegerlas de los enemigos es sumamente exigente y requiere mucha energía. Por fortuna, también puedes obtener energía de cada mina de oro. Cada una de estas minas genera una cantidad de energía .Tu objetivo es seleccionar un segmento contiguo de minas de oro y protegerlas, asegurándote de que puedas ganar la mayor cantidad de oro posible. Al elegir un segmento, necesitas tener al menos la misma cantidad de energía que la longitud de dicho segmento para poder protegerlo de los enemigos.
¿Cuánto oro se puede obtener de las minas?
Entrada
La primera línea de la entrada contiene un único entero
n (1 ≤ n ≤ ).Las siguientes
n líneas contienen 3 enteros separados por espacio (1 ≤ ≤ ), que representan la coordenada de la mina de oro, la cantidad de oro que produce y la cantidad de energía que genera. Todas las coordenadas son diferentes y se dan en orden creciente.Salida
El programa debe imprimir la cantidad máxima de oro que se puede obtener de manera segura de las minas de oro.
Ejemplos
Entrada | Salida |
4
1 5 1
2 7 2
5 4 1
8 15 1 | 16 |
2
1 4 1
4 5 1 | 5 |
Explicación
- El primer ejemplo → 16
X | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Energy | 1 | 2 | ㅤ | ㅤ | 1 | ㅤ | ㅤ | 1 |
Gold | 5 | 7 | ㅤ | ㅤ | 4 | ㅤ | ㅤ | 15 |
Puedes tomar las primeras 3 minas ⇒ La longitud del segmento es
5-1 = 4 (las minas están en los puntos extremos de las coordenadas), la energía que producen las minas es 1+2+1 = 4, y el oro obtenido asciende a 5+7+4 = 16.- El segundo ejemplo → 5
X | 1 | 2 | 3 | 4 |
Energy | 1 | ㅤ | ㅤ | 1 |
Gold | 4 | ㅤ | ㅤ | 5 |
Puedes escoger la última mina de oro ⇒ La longitud del segmento es
0, la energía que produce la mina es 1 y el oro obtenido es 5.Pista 1
Quizás necesites aplicar técnicas distintas en las partes izquierda y derecha cuando emplees un enfoque divide & conquer.
Pista 2
Intenta calcular las respuestas que pasan por el punto medio.
Constraints
Time limit: 8 seconds
Memory limit: 512 MB
Output limit: 1 MB