カズマ王国の陥落 [Kyoto University Programming Contest 2019 F]

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_f

前提知識

• 二次元累積和

解説

https://atcoder.jp/contests/kupc2019/submissions/7958884

最適方針として、なるべく1人の勇者に攻撃を集中させるのが得策。
なんとなくDP感がするので、DPで考えてみる。
dp[i] := 最後に勇者iに集中攻撃をした時のダメージ最大値
このように最後にどの勇者に集中攻撃したかが分かれば、勇者iを区間に持つ拠点とR[j]<iである拠点は使用済みとなる。
最後に集中攻撃をした勇者だけ覚えておけばよさそうだ。
するとN通りなので、ちょっと余裕がある。
遷移は普通にO(N)にしてみようか。
dp[i]→dp[i2]を考えると、i2は区間に入るが、iは区間に入らない拠点が総攻撃をする拠点になる。
これはi < L[j] ≦ i2、かつ、i2 ≦ R[j]を満たす拠点のモンスター総数が高速に求まればいい。
これは二次元累積和でいけるじゃん。
『かつおぶし』が脳裏をよぎるので、メモリを確認して出すと通る。

int N, A[3010], M;
ll dp[3010];
Ruisekiwa2D<3010, 3010> r2d;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    cin >> M;
    rep(i, 0, M) {
        int l, r, b; cin >> l >> r >> b;
        r2d.add(l, r, b);
    }
    r2d.build();

    rep(i, 0, N) {
        rep(j, i + 1, N + 1) {
            chmax(dp[j], dp[i] + r2d.get(i + 1, j, j, N) - A[j - 1]);
        }
    }

    ll ans = 0;
    rep(i, 0, N + 1) chmax(ans, dp[i]);
    cout << ans << endl;
}