Some Tanks Are in Siege Mode, Others Go Boom Boom Boom Boom Boom Boom!

Removing wasted siege attacks

A siege attack targeting either endpoint decreases total health by at most $3$, or at most $2$ when $N=1$. Attacks in tank mode can reproduce the same decreases for a cost of at most $3$. Therefore, an optimal solution exists that never targets an endpoint in siege mode.

A siege attack decreases the total health by at most $4$. If any damage is lost because health is clipped at $0$, its actual total decrease is at most $3$. Replace that attack with attacks in tank mode producing exactly the same decreases. This reaches the same state for a cost of at most $3$. Thus, an optimal solution exists in which every siege attack deals its full damage.

Maximizing the number of siege attacks

Let $x_i$ be the number of siege attacks targeting position $i$. By the observation above, omit endpoint attacks and set $x_0=x_1=x_N=x_{N+1}=0$. The following condition must hold at each position:

$$x_{i-1}+2x_i+x_{i+1}\le a_i.$$

Conversely, if these conditions hold, we can perform the siege attacks in any order without wasting damage, then remove the remaining health with attacks in tank mode. If $K=\sum_i x_i$, the siege attacks remove total health $4K$, and the total cost is

$$3K+\sum_{i=1}^{N}a_i-4K=\sum_{i=1}^{N}a_i-K.$$

It remains to maximize the sum of nonnegative integer values $x_i$ satisfying the conditions.

Dynamic programming

Let $M=\max_i a_i$ and $B=\lfloor M/2\rfloor$. Every lies between and .

Immediately before processing position $i$, let $\mathrm{dp}[p][q]$ be the maximum sum of the chosen values $x_1,\cdots,x_i$, assuming that all conditions before position hold and , . Impossible states have value negative infinity. Initially, and all other states are impossible.

Choose $r=x_{i+1}$. The current condition is $p+2q+r\le a_i$, giving the transition

$$\mathrm{next}[q][r]=r+\max_{0\le p\le\min(B,a_i-2q-r)}\mathrm{dp}[p][q].$$

Only $r=0$ is allowed when $i+1\ge N$. For each fixed $q$, compute prefix maxima along $p$ to evaluate each transition in $$ time. After processing position , is the maximum number of siege attacks.

The transitions enumerate every possible next count and check exactly the condition at the current position. Induction therefore proves that the DP preserves every feasible placement and its maximum count. The answer is $\sum_i a_i-\mathrm{dp}[0][0]$.

The time complexity is $O(N(B+1)^2)$ and the space complexity is $O((B+1)^2)$. Since , we have . Using also covers an all-zero input.

Subtasks

• Subtask $1$: Use the current health vector as a state and try both attack types directly. Time is $O(N\prod_i(a_i+1))$ and space is . With and , there are at most states.

Solution written by GPT6