[Codeforces] Codeforces Round #668 (Div. 2) B. Array Cancellation

2020年9月7日2020年12月13日

問題

方針

\( i < j \) のとき、\( a_i \leftarrow a_i – 1 \)、\( a_j \leftarrow a_j + 1\) という操作は \( 0 \) コストでできますが、\( i > j \) ではコストが \( 1 \) かかります。

前から順番に調べていき、\( a_i > 0 \) となる \( a_i \) の和を \( s \) とします。\( s \) が正であれば、\( a_i < 0 \) となる要素にたいして \( s \) までコストが掛からずに操作を行うことができます。

\( a_i < 0 \) のとき

\( a_i + s \geq 0 \) ならばノーコストで \( a_i = 0 \) とすることができます。また、\( s \leftarrow a_i + s \) と更新します。\( a_i + s < 0 \) のとき、\( -(a_i + s)\) のコストを払い \( a_i = 0 \) とすることができます。また、\( s = 0 \) となります。

\( a_i \geq 0 \) のとき

\( s \leftarrow a_i + s \) と更新します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a[100000]{};

ll solve(int n) {
    ll ret = 0;
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] <= 0) {
            if (sum + a[i] >= 0) {
                sum += a[i];
            } else {
                ret += -a[i] - sum;
                sum = 0;
            }
        } else {
            sum += a[i];
        }
    }
    return ret;
}

int main() {
    int t, n;
    cin >> t;
    ll ans[t]{};
    for (int i = 0; i < t; i++) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> a[j];
        }
        ans[i] = solve(n);
    }
    for (ll i : ans) {
        cout << i << "\n";
    }
    return 0;
}