No.1014 competitive fighting

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 : otamay6 / テスター : tpyneriver

問題文

otamayさんは格ゲープレイヤーです。今日も自分のメインキャラクターの研究をしているようです。
連続して相手に当てることができる技の繋がりのことをコンボと言います。
このゲームでは技を当てたあと、発生が直前に出した技の(威力)-(硬直)以下である別の技を出すことでコンボを伸ばすことができます。
以下の問いに答えて下さい

正整数 $N$ が与えられます。$N$ は技の数を表します。
各 $i\ (1 \le i \le N)$ について、技の発生 $A_i$, 技の威力 $B_i$, 技の硬直 $C_i$ が与えられます。
$N$ 個の技について、その技を始動とするコンボの、威力の総和の最大値をそれぞれ求めて下さい。
ただし、同じ技を続けて出すことはできないものとします。
無限にコンボが繋がる場合は BAN と出力して下さい。
より形式的には以下のような問題を解くことになります。

・$k_1 = i$
・$1 \le k_n \le N$ $(n \ge 2)$
・$A_{k_{n+1}} \le B_{k_n} - C_{k_n}$
・$k_{n+1} \neq k_n$

以上の条件を全て満たす長さ1以上の数列 {$k_1, \dots$} について
$\displaystyle \sum_{n \ge 1} B_{k_n}$ の最大値を各 $i\ (1 \le i \le N)$ についてそれぞれ求めて下さい。
答えが $\infty$ ならば BAN と出力してください。

$N$
$A_1\ B_1\ C_1$
$\vdots$
$A_N\ B_N\ C_N$

3
3 3 4
5 5 1
4 6 3

3
14
9

2
1 2 1
1 3 2

BAN
BAN

9
7 12 24
4 8 6
4 30 33
3 24 22
3 9 1
12 43 40
2 6 4
2 5 4
1 1 1

12
20
30
36
45
88
12
6
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。