일부는 시즈모드 됐고 일부는 퉁퉁퉁퉁퉁퉁!

낭비되는 공성 공격 제거

양 끝 위치를 대상으로 하는 공성 공격은 체력의 합을 최대 $3$만큼 내린다. $N=1$이면 최대 $2$만큼 내린다. 같은 체력 감소를 전차 모드의 공격들로 비용 $3$ 이하에 재현할 수 있으므로, 양 끝을 대상으로 하는 공성 공격을 사용하지 않는 최적해가 존재한다.

공성 모드의 공격 한 번은 체력을 최대 $4$만큼 내린다. 체력 $0$에서 잘려 피해가 하나라도 낭비되었다면 실제로 내린 체력의 합은 $3$ 이하이다. 그 공격을 실제로 내린 체력만큼의 전차 모드 공격으로 대체하면 같은 상태를 비용 $3$ 이하로 만들 수 있다. 따라서 최적해는 모든 공성 공격의 피해가 온전히 적용되는 형태로 잡을 수 있다.

공성 공격의 횟수 최대화

$i$번 위치를 대상으로 하는 공성 공격의 횟수를 $x_i$라 하자. 위의 관찰에 따라 양 끝의 공격을 제외하고, $x_0=x_1=x_N=x_{N+1}=0$으로 둔다. 각 위치에서 다음 조건을 만족해야 한다.

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

이 조건이 성립하면 공성 공격들을 어떤 순서로 하더라도 피해가 낭비되지 않는다. 남은 체력은 전차 모드로 처리할 수 있다. $K=\sum_i x_i$라 하면 공성 공격이 체력의 합을 $4K$만큼 줄이므로 총비용은

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

이다. 따라서 위 조건을 만족하는 정수 $x_i\ge0$의 합을 최대화하면 된다.

동적 계획법

$M=\max_i a_i$, $B=\lfloor M/2\rfloor$라 하자. 모든 는 이상 이하이다.

$i$번 위치를 처리하기 직전의 $\mathrm{dp}[p][q]$를 다음과 같이 정의한다. $i-1$번 위치까지의 조건을 만족하고 $x_{i-1}=p$, 일 때, 이미 정한 의 합의 최댓값이다. 불가능한 상태는 음의 무한대로 둔다. 처음에는 이고 나머지는 불가능하다.

$r=x_{i+1}$을 정하면 $p+2q+r\le a_i$를 만족해야 하므로 전이는

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

가 된다. $i+1\ge N$이면 $r=0$만 허용한다. $q$를 고정하고 $p$ 방향의 누적 최댓값을 구하면 각 전이를 $$에 계산할 수 있다. 마지막 번 위치까지 처리한 뒤 이 공성 공격 횟수의 최댓값이다.

모든 가능한 다음 횟수를 확인하고 정확히 현재 위치의 체력 조건을 검사하므로, 귀납적으로 DP는 가능한 모든 공성 공격 배치와 그 최댓값을 보존한다. 따라서 $\sum_i a_i-\mathrm{dp}[0][0]$이 정답이다.

시간 복잡도는 $O(N(B+1)^2)$, 공간 복잡도는 $O((B+1)^2)$이다. 이므로 이다. 원소가 모두 인 경우에도 로 표기한 복잡도가 유효하다.

서브태스크

• 서브태스크 $1$: 현재 체력 벡터를 상태로 두고 두 공격을 직접 시도한다. 시간은 $O(N\prod_i(a_i+1))$, 공간은 이다. , 이므로 상태 수는 최대 이다.

Solution written by GPT6