鉱山を守る
ビデオゲームでは、資源管理がとても重要です。
異なる場所 に n 個の金鉱があります。各金鉱は、それぞれ一定量の gold を生産します。しかし、これらの金鉱を敵から守るには多くの energy が必要です。ただ幸いなことに、それぞれの金鉱からも一定量の energy を得ることができます。
あなたは、連続した金鉱の区間を選んで保護しつつ、できるだけ多くの gold を得たいと考えています。区間を選ぶ際には、その区間の長さ以上の energy を確保しなければ、敵から守りきることはできません。
最終的に得られる gold の最大量はどれくらいでしょうか？
入力
入力の最初の行には、整数 n (1 ≤ n ≤ ) が1つ与えられます。
続く n 行には、3 つの空白区切り整数 (1 ≤ ≤ ) が与えられます。これはそれぞれ、金鉱の座標、金鉱が生産する gold の量、そして生産される energy の量を表します。すべての座標は異なり、昇順で与えられます。
出力
安全に得ることができる gold の最大量を出力してください。
例
入力 | 出力 |
|---|---|
4 | 16 |
2 | 5 |
解説
最初の例 → 16
X
1
2
3
4
5
6
7
8
Energy
1
2
1
1
Gold
5
7
4
15
最初の 3 つの金鉱を選ぶ場合 ⇒ この区間の長さは
5-1 = 4（区間の両端座標の差）となり、金鉱から得られる energy は1+2+1 = 4、そして得られる gold は5+7+4 = 16となります。
二番目の例 → 5
X
1
2
3
4
Energy
1
1
Gold
4
5
最後の金鉱だけを選ぶ場合 ⇒ 区間の長さは
0、金鉱が生み出す energy は1、そして得られる gold は5です。
Hint 1
Divide & Conquer を実行する際、左半分と右半分で異なる手法を組み合わせる必要があるかもしれません。
Hint 2
真ん中の境界付近をまたいだ解を計算してみるとよいでしょう。
Constraints
Time limit: 8 seconds
Memory limit: 512 MB
Output limit: 1 MB