Proteger as minas
Quando se joga videojogos, a gestão de recursos é fundamental.
Existem
n minas de ouro em diferentes localizações . Cada uma delas pode produzir uma certa quantidade de ouro . No entanto, proteger essas minas contra inimigos exige muita energia. Felizmente, também é possível obter energia de cada mina de ouro, representada por .O objetivo é selecionar um segmento contíguo de minas de ouro e protegê-lo, garantindo o maior ganho de ouro possível. Ao escolher esse segmento, é necessário ter pelo menos a mesma quantidade de energia que o comprimento do segmento para conseguir protegê-lo dos inimigos.
Quanto ouro seria possível obter das minas?
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ).As próximas
n linhas contêm 3 inteiros separados por espaço (1 ≤ ≤ ): a coordenada da mina de ouro, a quantidade de ouro que ela pode produzir e a quantidade de energia que ela produz. Todas as coordenadas são garantidamente diferentes e são fornecidas em ordem crescente.Saída
O programa deve imprimir a quantidade máxima de ouro que é possível obter de forma segura.
Exemplos
Entrada | Saída |
4
1 5 1
2 7 2
5 4 1
8 15 1 | 16 |
2
1 4 1
4 5 1 | 5 |
Explicação
- O primeiro exemplo → 16
X | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Energy | 1 | 2 | ㅤ | ㅤ | 1 | ㅤ | ㅤ | 1 |
Gold | 5 | 7 | ㅤ | ㅤ | 4 | ㅤ | ㅤ | 15 |
Pode-se escolher as primeiras 3 minas ⇒ O comprimento do segmento seria
5-1 = 4 (considerando as minas nos limites dessas coordenadas). A energia produzida pelas minas seria 1+2+1 = 4, e o ouro obtido seria 5+7+4 = 16.- O segundo exemplo → 5
X | 1 | 2 | 3 | 4 |
Energy | 1 | ㅤ | ㅤ | 1 |
Gold | 4 | ㅤ | ㅤ | 5 |
Pode-se selecionar apenas a última mina de ouro ⇒ O comprimento do segmento é
0, a energia produzida pela mina é 1, e o ouro obtido seria 5.Dica 1
Talvez seja necessário aplicar técnicas diferentes nas partes esquerda e direita ao utilizar uma abordagem de dividir e conquistar.
Dica 2
Pode tentar calcular as respostas que passam pelo ponto médio.
Constraints
Time limit: 8 seconds
Memory limit: 512 MB
Output limit: 1 MB