[Codeforces] 1285B: Just Eat It!

 

이 문제는 prefix sum 알고리즘으로 풀어야 하는 문제이다.

 

소스코드

 

#include <bits/stdc++.h>
using namespace std;
 
int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    long long a[100001];
    long long p[100001];
    long long m[100001]; // a[i]에서 끝나는 제일 큰 합
 
    long long t, n, total, mn, ans;
    cin >> t;
    while (t > 0) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        p[0] = 0;
        for (int i = 1; i <= n; i++) {
            p[i] = p[i-1] + a[i];
        }
        total = p[n];
        ans = 1;
 
        mn = 0;
        for (int i = 1; i < n; i++) {
            m[i] = p[i] - mn;
            mn = min(mn, p[i]);
            if (m[i] >= total) ans = 0;
 
        }
        for (int i = 1; i <= n; i++) {
            p[i] -= a[1];
        }
        mn = 0;
        for (int i = 2; i <= n; i++) {
            m[i] = p[i] - mn;
            mn = min(mn, p[i]);
            if (m[i] >= total) ans = 0;
 
        }
        if (ans == 1) cout << "YES" << endl;
        else cout << "NO" << endl;
 
        t--;
    }
 
    return 0;
 
}