City Savers [AtCoder Beginner Contest 135 C]

https://atcoder.jp/contests/abc135/tasks/abc135_c

解説

https://atcoder.jp/contests/abc135/submissions/6588408

どこから考えようかという問題。
DPを考えてみると、dp[i][rest] := i人目までの勇者が倒し終わっていて、最後の街にrest体のモンスターがいるがある。
だが、これは300点問題には難しそうな感じがする。
制約にも弱点がないので、貪欲法で実は解けるパターンかと推測。

1番目の街は勇者1が担当するしかないので、なるべく勇者1が倒して、余力があれば2番目の街を担当する。
2番目の街はそうすると勇者2が担当するしかないので、なるべく勇者2が倒して、余力があれば3番目の街を担当する。
これをどんどん続けていく貪欲を書こう。

int N, A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N + 1) cin >> A[i];
    rep(i, 0, N) cin >> B[i];

    ll ans = 0;
    rep(i, 0, N) {
        ll lft = min(A[i], B[i]);

        ans += lft;
        A[i] -= lft;
        B[i] -= lft;

        ll rht = min(A[i + 1], B[i]);

        ans += rht;
        A[i + 1] -= rht;
        B[i] -= rht;
    }
    cout << ans << endl;
}