Proteggere le miniere
Quando si gioca ai videogiochi, la gestione delle risorse è essenziale.
Ci sono
n miniere d’oro situate in diverse coordinate . Ognuna di queste miniere può produrre una certa quantità d’oro . Tuttavia, difenderle dai nemici richiede molta energia. Fortunatamente, è possibile ottenere energia anche da ogni singola miniera d’oro, poiché ciascuna produce una quantità di energia pari a .Si desidera selezionare un intervallo contiguo di miniere e proteggerle, in modo da massimizzare la quantità d’oro guadagnata. Quando si sceglie un intervallo, è necessario avere almeno tanta energia quanto è la lunghezza dell’intervallo per poterlo difendere.
Qual è la massima quantità d’oro che si può ottenere dalle miniere?
Input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ ).Le successive
n righe contengono 3 interi separati da uno spazio, ossia (1 ≤ ≤ ), dove è la coordinata della miniera d’oro, è la quantità di oro che produce, ed è la quantità di energia che fornisce. Tutte le coordinate sono diverse tra loro e sono fornite in ordine crescente.Output
Il programma deve stampare la massima quantità d’oro che si può ottenere in sicurezza dalle miniere.
Esempi
Ingresso | Uscita |
4
1 5 1
2 7 2
5 4 1
8 15 1 | 16 |
2
1 4 1
4 5 1 | 5 |
Spiegazione
- Primo esempio → 16
X | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Energy | 1 | 2 | ㅤ | ㅤ | 1 | ㅤ | ㅤ | 1 |
Gold | 5 | 7 | ㅤ | ㅤ | 4 | ㅤ | ㅤ | 15 |
È possibile prendere le prime 3 miniere ⇒ la lunghezza dell’intervallo è
5-1 = 4 (le miniere sono agli estremi delle coordinate), l’energia prodotta dalle miniere è 1+2+1 = 4 e la quantità di oro ricavata è 5+7+4 = 16.- Secondo esempio → 5
X | 1 | 2 | 3 | 4 |
Energy | 1 | ㅤ | ㅤ | 1 |
Gold | 4 | ㅤ | ㅤ | 5 |
Si può selezionare l’ultima miniera d’oro ⇒ la lunghezza dell’intervallo è
0, l’energia prodotta dalla miniera è 1 e l’oro ottenuto è 5.Hint 1
Potrebbe essere necessario applicare tecniche diverse nella parte sinistra e in quella destra durante un approccio di tipo divide & conquer.
Hint 2
Si può provare a calcolare le risposte che attraversano il punto mediano.
Constraints
Time limit: 8 seconds
Memory limit: 512 MB
Output limit: 1 MB