満点解法です。

この問題を解くために、以下のような DP を行うことを考えます。

\(dp[i][j]\) := \(i\) 番目までの敵を攻撃 \(1\) によって倒し終えていて、攻撃 \(2\) を \(j\) 回した場合の、貰える勲章の枚数の最大値。

この DP は、以下のように更新できます。

// get(n) := n ダメージ与えた時に、貰える勲章の数
// cnt(l,r,k) := h[l] ~ h[r] の中で、k 以上であるものの数
// 更新式 1.
dp[i+1][j] = max(dp[i+1][j], dp[i][j] + get(h[i+1]-j));
// 更新式 2.
dp[i][j+1] = max(dp[i][j+1], dp[i][j] + get(cnt(i+1,n,j+1)));

この DP を純粋に更新していては間に合わないので、更新を in-line に行うことを考えます。

上記の更新式を整理すれば、結局以下の \(4\) 種類の更新を順番に行えば良いです。

• \(j \le a_1 (\le a_2)\) を満たす \(j\) について、\(j\) の小さい順に、\(dp[j]\) を \(\max (dp[j], dp[j - 1] + 2)\) で更新する。
• \(j \le a_2\) を満たす \(j\) について、\(j\) の小さい順に、\(dp[j]\) を \(\max (dp[j], dp[j - 1] + 1)\) で更新する。
• \(j \le a_3\) を満たす \(j\) について、\(dp[j]\) を インクリメントする。その後、\(j\) の小さい順に、\(dp[j]\) を \(\max (dp[j], dp[j - 1])\) で更新する。
• \(j \le a_4\) を満たす \(j\) について、\(dp[j]\) を インクリメントする。その後、\(j\) の小さい順に、\(dp[j]\) を \(\max (dp[j], dp[j - 1])\) で更新する。

DP の値そのものではなく、\(dp[i] - dp[i - 1] \ge 1\) と　\(dp[i] - dp[i - 1] \ge 2\) となっている場所をそれぞれ set などのデータ構造を用いて管理します（前者の集合の管理を \(s_1\) 、後者を \(s_2\) で行うとします）。すると、上記の \(4\) 種類の更新と対応する、行うべき処理は以下のようになります。

• \(s_1, s_2\) の両方に、\(a_1 (\le a_2)\) 以下の全ての値が存在するようになるまで、以下を行う。
  • \(s_1, s_2\) の要素のうち \(a_1\) より大きい最小のものを削除する。（そのような要素が存在しないなら、何もしない。）
  • \(a_1\) 以下の値で、\(s_1, s_2\) に存在していなかった要素を挿入する。
• \(s_1\) に、\(a_2\) 以下の全ての値が存在するようになるまで、以下を行う。
  • （\(s_1\) の要素のうち \(a_2\) より大きい最小のもの、\(s_2\) の要素のうち 挿入しようとしているものより大きい最小の要素）のうち小さい方を削除する。（そのような要素が存在しないなら、何もしない。）
  • \(a_2\) 以下の値で、\(s_1\) に存在していなかった要素を挿入する。
• \(s_1, s_2\) の要素のうち \(a_3\) より大きい最小のものを削除する（どちらにも入っている場合には、\(s_2\) からの削除を優先する）。\(dp[0]\) の値をインクリメントする。
• \(s_1, s_2\) の要素のうち \(a_4\) より大きい最小のものを削除する（どちらにも入っている場合には、\(s_2\) からの削除を優先する）。\(dp[0]\) の値をインクリメントする。

ここで、更新式 \(2.\) を観察すると、上記の操作に登場する \(a_1, a_2\) の値は単調減少であることが分かります。よって適切な実装（例えば、\(s_1, s_2\) の中に入っていない要素もまた、setなどを用いて管理する）をすると上記の \(4\) 種類の操作は全て償却 \(O(\log N)\) 時間で行うことができます。

最終的に、インクリメントした \(dp[0]\) の値と、管理している要素の数の合計が DP 配列に登場する最大値と一致し、これが答えとなります。