この問題はダブリングを用いて解くことができます。

魔力増減の絶対値の最大値を \(L\) とします。

公式解説冒頭と同様の考察により、敵を倒す直前、「最後に \(C_i>0\) の技を使ったとき以降」を除いて、魔力が \(2L\) 以上溜まった状態になることはないとして良いです（そうなる前に魔力を消費する技を使えばいいため）。このことはつまり、全てのタイミングにおいて、魔力は \(2L\) を上限としてそれ以上増えることはないとして良いということです。

ここで
\(DP[k][x]=\) 技を \(2^k\) 回使って、トータルでの魔力の増加量が \(x\) であるときの最大ダメージ
というDPテーブルを考えます。前述の考察から、\(x\) は\(-2L\) 以上 \(2L\) 以下の範囲のみ考えれば十分です。

（真に考えるべきは「技を \(2^k\) 回使って、トータルでの魔力の増加量が \(x\) で、技の列のどのprefixにおける魔力の増加量も \(\min(0,x)\) 以上であるときの最大ダメージ 」ですが、技の順序を適切に並び替えることで prefix に関する条件は常に満たせることがわかるため、無視して良いです）

\(DP[k][*]\) から \(DP[k+1][*]\) の必要な範囲を計算することは \(O(L^2)\) でできます。また、全ての \(i\) で \(D_i\geq 1\) であることから必要な行動回数は明らかに \(H\) 以下であるため、\(k\leq \log H\) の範囲がわかっていれば十分です。

DPテーブルの値が既知のとき \(O(L^2\log H)\) で答えを求めることができるため、問題全体を \(O(N+L^2\log H)\) で解くことができました。

実装例(C)
実装例(C++)

お好みで、DPを累積和の形にする、すなわち
\(DP[k][x]=\) 技を \(2^k\) 回使って、魔力の増加量が \(x\) 以上であるときの最大ダメージ
とするといくらか実装が簡単になる場合があります。