vJwfgl - Online C++0x Compiler & Debugging Tool

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<long long> pref(2*n+1, 0);

    for (int i = 1; i <= n; i++)
        pref[i] = pref[i-1] + a[i-1];

    for (int i = n+1; i <= 2*n; i++)
        pref[i] = pref[n] + pref[i-n];

    deque<int> dq;
    vector<long long> mn(2*n+1);

    int len = n;

    for (int i = 1; i <= 2*n; i++) {
        while (!dq.empty() && pref[dq.back()] >= pref[i]) dq.pop_back();
        dq.push_back(i);
        while (dq.front() <= i - len) dq.pop_front();

        mn[i] = pref[dq.front()];
    }

    int ans = 0;

    for (int k = 1; k <= n; k++) {
        long long low = mn[k + n - 1];
        if (low >= pref[k-1]) ans++;
    }

    cout << ans << "\n";
}