3841번: Non-negative Partial Sums - 다르게 풀기

https://www.acmicpc.net/problem/3841

#include<stdio.h>
#include<deque>
using namespace std;
const int MAX_N = 1e6;
int n, s[2 * MAX_N];
deque<int> dq;
void push(int x) {
    while (dq.size() && s[dq.back()] > s[x]) dq.pop_back();
    dq.push_back(x);
    if (dq.front() <= x - n) dq.pop_front();
}
int main() {
    for (;;) {
        scanf("%d", &n);
        if (!n) break;
        int r = 0;
        dq.clear();
        for (int i = 0; i <n; i++) scanf("%d", s + i), s[i + n] = s[i];
        for (int i = 1; i < 2 * n; i++) s[i] += s[i - 1];
        for (int i = 0; i <n; i++) push(i);
        for (int i = n; i < 2 * n; i++) {
            push(i);
            if (s[dq.front()] >= s[i - n]) r++;
        }
        printf("%d\n", r);
    }
    return 0;
}