Schutz der Minen
Beim Spielen von Videospielen ist ein effektives Ressourcenmanagement unverzichtbar.
Es gibt
n Goldminen an verschiedenen Positionen . Jede dieser Minen kann eine bestimmte Menge Gold produzieren. Allerdings ist es sehr aufwendig, diese Minen vor Feinden zu schützen, da dafür viel Energie benötigt wird. Glücklicherweise liefert jede Goldmine auch Energie: Jede Mine produziert eine bestimmte Menge Energie .Jetzt möchtest du einen zusammenhängenden Abschnitt von Goldminen auswählen und sie beschützen, um möglichst viel Gold zu erhalten. Wenn du einen solchen Abschnitt auswählst, brauchst du mindestens so viel Energie, wie der Abschnitt lang ist, um ihn wirksam verteidigen zu können.
Wie viel Gold kann insgesamt sicher aus den Minen gewonnen werden?
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne Ganzzahl
n (1 ≤ n ≤ ).Die nächsten
n Zeilen enthalten jeweils 3 durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ ): die Koordinate der Goldmine, wie viel Gold sie produziert und wie viel Energie sie liefert. Alle Koordinaten sind verschieden und aufsteigend sortiert.Ausgabe
Das Programm soll die maximale Menge an Gold ausgeben, die sicher aus den Goldminen gewonnen werden kann.
Beispiele
Eingabe | Ausgabe |
4
1 5 1
2 7 2
5 4 1
8 15 1 | 16 |
2
1 4 1
4 5 1 | 5 |
Erklärung
- Das erste Beispiel → 16
X | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Energy | 1 | 2 | ㅤ | ㅤ | 1 | ㅤ | ㅤ | 1 |
Gold | 5 | 7 | ㅤ | ㅤ | 4 | ㅤ | ㅤ | 15 |
Hier kann man die ersten drei Minen nehmen ⇒ Die Länge des gewählten Abschnitts entspricht
5-1 = 4 (da die Minen an den Endpunkten liegen). Die von den Minen produzierte Energie ist 1+2+1 = 4, und die Goldmenge beträgt 5+7+4 = 16.- Das zweite Beispiel → 5
X | 1 | 2 | 3 | 4 |
Energy | 1 | ㅤ | ㅤ | 1 |
Gold | 4 | ㅤ | ㅤ | 5 |
Hier kann man die letzte Goldmine auswählen ⇒ Die Länge des Abschnitts ist
0, die produzierte Energie der Mine beträgt 1, und das gewonnene Gold 5.Tipp 1
Es kann sinnvoll sein, unterschiedliche Verfahren für den linken und rechten Teil in einer Divide-&-Conquer-Strategie anzuwenden.
Tipp 2
Man kann versuchen, die Lösungen zu berechnen, die durch den Mittelpunkt gehen.
Constraints
Time limit: 8 seconds
Memory limit: 512 MB
Output limit: 1 MB