No.1014 competitive fighting
タグ : / 解いたユーザー数 34
作問者 :
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$
入力は全て整数で与えられる。
$1 \le N \le 10^5$
$1 \le A_i,B_i,C_i \le 10^9$
出力
各 $i(1 \le i \le N)$ について、答えを改行区切りで出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 3 3 4 5 5 1 4 6 3
出力
3 14 9
技2→技3→技1の順にコンボを決めることができます。
技1はコンボの派生先が存在しないので、技1の威力である3がそのまま答えとなります。
サンプル2
入力
2 1 2 1 1 3 2
出力
BAN BAN
格ゲーの世界では無限コンボをしてしまうと出禁になります。
サンプル3
入力
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もしくは右上の雲マークをクリックしてアカウントを作成してください。