[알고연] (2주차-3) 1285B. Just Eat It!

1285B. Just Eat It!

Today, Yasser and Adel are at the shop buying cupcakes. There are nn cupcake types, arranged from 11 to nn on the shelf, and there are infinitely many of each type. The tastiness of a cupcake of type ii is an integer aiai. There are both tasty and nasty cupcakes, so the tastiness can be positive, zero or negative.

Yasser, of course, wants to try them all, so he will buy exactly one cupcake of each type.
On the other hand, Adel will choose some segment [l,r] (1≤l≤r≤n) that does not include all of cupcakes (he can't choose [l,r]=[1,n]) and buy exactly one cupcake of each of types l,l+1,…,r.

After that they will compare the total tastiness of the cupcakes each of them have bought. Yasser will be happy if the total tastiness of cupcakes he buys is strictly greater than the total tastiness of cupcakes Adel buys regardless of Adel's choice.

For example, let the tastinesses of the cupcakes be [7,4,−1]. Yasser will buy all of them, the total tastiness will be 7+4−1=10. Adel can choose segments[7],[4],[−1],[7,4] or [4,−1], their total tastinesses are 7,4,−1,11 and 33, respectively. Adel can choose segment with tastiness 11, and as 10 is not strictly greater than 11, Yasser won't be happy :(

Find out if Yasser will be happy after visiting the shop.

 

누적합 + DP 문제로 생각해내기가 까다로운 문제다. 거기다 [1, n] 전체 구간은 제외해야 한다는 조건 때문에 [1, n-1]과 [2, n]으로 경우를 나눠 생각해야 해서 이 문제가 백준에 나왔다면 골드2 ~ 골드1 정도로 꽤 어려운 레벨이 되지 않을까 싶다.

minimum에는 지금까지 본 누적합들 중 최솟값이 들어가있고, dp에는 i번째 값까지 봤을 때 나올 수 있는 가장 최대의 tasteness 가 저장된다. 즉 구간 [1, n-1] 에서는 dp[n-1] 값이 total 값보다 작고, 구간 [2, n] 에서는 dp[n] 값이 total 값보다 작아야 "YES"가 출력된다. 이때 구간 [2, n]의 경우 첫번째 값을 누적합에서 제외시키고 계산해야 한다는 점을 주의하자.

#include <bits/stdc++.h>

using namespace std;

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

    int t; cin >> t;
    while (t--) {

        int n; cin >> n;
        long long total = 0, minimum = 0;
        bool ans = true;

        // Prefix Sum
        vector<long long> vec(n), psum(n + 1), dp(n + 1);
        for (int i = 0; i < n; i++) cin >> vec[i];
        psum[0] = 0;
        for (int i = 1; i <= n; i++) psum[i] = psum[i - 1] + vec[i - 1];

        // Calculate [1, n-1]
        total = psum[n];
        for (int i = 1; i < n; i++) {
            dp[i] = psum[i] - minimum;
            minimum = min(minimum, psum[i]); // minimum of psums
            if (dp[i] >= total) ans = false;
        }
        
        // Calculate [2, n]
        // Preprocessing: except vec[0] 
        minimum = 0;
        for (int i = 1; i <= n; i++) psum[i] -= vec[0];

        for (int i = 2; i <= n; i++) {
            dp[i] = psum[i] - minimum;
            minimum = min(minimum, psum[i]);
            if (dp[i] >= total) ans = false;
        }

        cout << (ans ? "YES\n" : "NO\n");
    }
    return 0;
}