Protéger les mines
Lorsqu’on joue à des jeux vidéo, la gestion des ressources est essentielle.
Il existe
n mines d’or à des emplacements distincts . Chacune de ces mines peut produire une certaine quantité d’or . Cependant, les protéger contre les ennemis demande énormément d’énergie. Heureusement, on peut aussi obtenir de l’énergie de chacune de ces mines. Chaque mine produit une certaine quantité d’énergie .Vous souhaitez sélectionner un segment contigu de mines d’or et les protéger afin de récolter le plus d’or possible. Pour choisir un segment, il vous faut disposer d’une quantité d’énergie au moins égale à la longueur de ce segment pour pouvoir le défendre contre les ennemis.
Quelle quantité d’or est-il possible d’obtenir au maximum à partir de ces mines?
Entrée
La première ligne de l’entrée contient un seul entier
n (1 ≤ n ≤ ).Les
n lignes suivantes contiennent chacune 3 entiers séparés par des espaces (1 ≤ ≤ ). Il s’agit de la coordonnée de la mine d’or, de la quantité d’or qu’elle peut produire et de la quantité d’énergie qu’elle produit. Toutes les coordonnées sont différentes et sont données dans l’ordre croissant.Sortie
Le programme doit afficher la quantité maximale d’or pouvant être obtenue en toute sécurité à partir des mines d’or.
Exemples
Entrée | Sortie |
4
1 5 1
2 7 2
5 4 1
8 15 1 | 16 |
2
1 4 1
4 5 1 | 5 |
Explication
- Le premier exemple → 16
X | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Energy | 1 | 2 | ㅤ | ㅤ | 1 | ㅤ | ㅤ | 1 |
Gold | 5 | 7 | ㅤ | ㅤ | 4 | ㅤ | ㅤ | 15 |
Vous pouvez prendre les 3 premières mines ⇒ La longueur du segment serait
5-1 = 4 (les mines se trouvant aux coordonnées de ses bornes), l’énergie produite par ces mines serait 1+2+1 = 4, et la quantité d’or obtenue s’élèverait à 5+7+4 = 16.- Le deuxième exemple → 5
X | 1 | 2 | 3 | 4 |
Energy | 1 | ㅤ | ㅤ | 1 |
Gold | 4 | ㅤ | ㅤ | 5 |
Vous pouvez choisir la dernière mine d’or ⇒ La longueur du segment est
0, l’énergie produite par cette mine est 1 et la quantité d’or obtenue est 5.Indice 1
Vous pourriez avoir besoin d’appliquer différentes techniques aux parties gauche et droite dans le cadre d’une approche de division et conquête.
Indice 2
Vous pouvez essayer de calculer les réponses qui passent par le point médian.
Constraints
Time limit: 8 seconds
Memory limit: 512 MB
Output limit: 1 MB