Submission #9872631

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)

typedef long long LL;
typedef pair<int, int> pii;

const int INTINF = 1e9;
const LL LLINF = 1e18;

void solve()
{
    int N;
    cin >> N;
    vector<int> a(N);

    REP0(i, N)
    {
        cin >> a[i];
    }
    LL ans = LLINF;

    { // 偶数番目までの累積を正にする
        LL ans_e = 0;
        LL sign[2] = {1, -1};
        LL cumsum = 0;
        REP0(i, N)
        {
            cumsum += a[i];
            if (cumsum * sign[i % 2] <= 0)
            {
                ans_e += abs(cumsum) + 1;
                cumsum = sign[i % 2];
            }
        }
        ans = min(ans_e, ans);
    }

    { // 奇数番目までの累積を正にする
        LL ans_o = 0;
        LL sign[2] = {-1, 1};
        LL cumsum = 0;
        REP0(i, N)
        {
            cumsum += a[i];
            if (cumsum * sign[i % 2] <= 0)
            {
                ans_o += abs(cumsum) + 1;
                cumsum = sign[i % 2];
            }
        }
        ans = min(ans_o, ans);
    }
    cout << ans << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}

Submission Info

Judge Result