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 | 16 |
2 | 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 = 4e 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 è1e 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