No.1014 competitive fighting
タグ : / 解いたユーザー数 32
作問者 :
otamay6
/ テスター :
tpyneriver
Problem Statement
otamay is a fighting game player. It seems that today, too, otamay is researching their main character.
A chain of moves that can be landed on the opponent consecutively is called a combo.
In this game, after landing a move, you can extend the combo by performing a different move whose startup is at most (power) - (recovery) of the move performed immediately before.
Answer the following question.
You are given a positive integer $N$. $N$ represents the number of moves.
For each $i\ (1 \le i \le N)$, the startup $A_i$, the power $B_i$, and the recovery $C_i$ of the move are given.
For each of the $N$ moves, find the maximum total power of a combo that starts with that move.
However, the same move cannot be performed twice in a row.
If the combo can continue infinitely, output BAN.
More formally, you are to solve the following problem.
・$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$
Over all sequences {$k_1, \dots$} of length at least 1 satisfying all of the above conditions,
find the maximum value of $\displaystyle \sum_{n \ge 1} B_{k_n}$ for each $i\ (1 \le i \le N)$.
If the answer is $\infty$, output BAN.
Input
$N$ $A_1\ B_1\ C_1$ $\vdots$ $A_N\ B_N\ C_N$
All inputs are integers.
$1 \le N \le 10^5$
$1 \le A_i,B_i,C_i \le 10^9$
Output
For each $i(1 \le i \le N)$, output the answer, separated by newlines.
Print a newline at the end.
Sample
Sample 1
Input
3 3 3 4 5 5 1 4 6 3
Output
3 14 9
You can perform a combo in the order move 2 → move 3 → move 1.
Move 1 has no move to continue the combo into, so its power, 3, is the answer as is.
Sample 2
Input
2 1 2 1 1 3 2
Output
BAN BAN
In the world of fighting games, performing an infinite combo gets you banned.
Sample 3
Input
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
Output
12 20 30 36 45 88 12 6 1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。