Защита шахт
Во время игры в видеоигры крайне важно грамотно управлять ресурсами.
Существует
n золотых шахт, расположенных в различных точках . Каждая из этих шахт способна приносить некоторое количество золота . Однако охранять эти шахты от врагов очень непросто и требует больших энергетических затрат. К счастью, каждая из них также вырабатывает энергию .Ваша задача — выбрать непрерывный отрезок из золотых шахт и защитить его, чтобы при этом заработать как можно больше золота. Для защиты выбранного отрезка необходимо обладать хотя бы таким количеством энергии, которое равно длине этого отрезка.
Какое максимальное количество золота удастся получить из шахт?
Входные данные
Первая строка входных данных содержит одно целое число
n (1 ≤ n ≤ ).В следующих
n строках содержатся три разделённых пробелами целых числа (1 ≤ ≤ ), где указаны координата золотой шахты, объём добываемого ею золота и количество вырабатываемой ею энергии. Гарантируется, что все координаты различны и расположены в порядке возрастания.Выходные данные
Программа должна вывести максимально возможное количество золота, которое можно безопасно добыть из золотых шахт.
Примеры
Входные данные | Выходные данные |
4
1 5 1
2 7 2
5 4 1
8 15 1 | 16 |
2
1 4 1
4 5 1 | 5 |
Пояснение
- Первый пример → 16
X | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Energy | 1 | 2 | ㅤ | ㅤ | 1 | ㅤ | ㅤ | 1 |
Gold | 5 | 7 | ㅤ | ㅤ | 4 | ㅤ | ㅤ | 15 |
Можно взять первые три шахты ⇒ длина отрезка будет
5-1 = 4 (шахты находятся по краям этого отрезка), суммарная вырабатываемая ими энергия составит 1+2+1 = 4, а общее количество добытого золота — 5+7+4 = 16.- Второй пример → 5
X | 1 | 2 | 3 | 4 |
Energy | 1 | ㅤ | ㅤ | 1 |
Gold | 4 | ㅤ | ㅤ | 5 |
Здесь можно выбрать только последнюю шахту ⇒ длина отрезка равна
0, она даёт 1 единицу энергии, а золота получится получить 5.Подсказка 1
Возможно, при использовании подхода «разделяй и властвуй» (divide & conquer), вам придётся применять разные техники для левой и правой частей задачи.
Подсказка 2
Попробуйте вычислить ответы, которые проходят через центральную точку (midpoint).
Constraints
Time limit: 8 seconds
Memory limit: 512 MB
Output limit: 1 MB