Official

D - Snuke Panic (1D) Editorial by en_translator


The problem can be solved with the following DP (Dynamic Programming):

\(DP[x][t] = \) The maximum sum of size of Snukes that Takahashi captures until he reaches at the coordinate \(x\) at time \(t\)

The transition is:

\(DP[x][t]=\max(DP[x-1][t-1],DP[x][t-1],DP[x+1][t-1]) + \text{the size of Snuke he can capture if he is at the coordinate }x\text{ at time }t.\)

Sample code (C)
Sample code (Python)

posted:
last update: