Submission #1329406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1329406		jochis	Feast (NOI19_feast)	C++20	Compilation error	0 ms	0 KiB

feast

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {

    int n, k;
    cin >> n >> k;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    bool allNonNeg = true;
    long long totalSum = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] < 0) allNonNeg = false;
        totalSum += a[i];
    }

    if (allNonNeg) {
        cout << totalSum << endl;
        return 0;
    }
    int negCount = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] < 0) negCount++;
    }

    if (negCount <= 1) {
        long long sumLeft = 0, sumRight = 0;
        int negPos = -1;
        for (int i = 1; i <= n; i++) {
            if (a[i] < 0) { negPos = i; break; }
        }
        if (negPos == -1) {
            cout << totalSum << endl;
            return 0;
        }
        for (int i = 1; i < negPos; i++) sumLeft += a[i];
        for (int i = negPos + 1; i <= n; i++) sumRight += a[i];

        long long ans = 0;
        ans = max(ans, sumLeft);
        ans = max(ans, sumRight);
        ans = max(ans, totalSum);
        ans = max(ans, sumLeft + sumRight);
        if (k == 1) {
            ans = max({(long long)0, sumLeft, sumRight, totalSum});
        } else {
            ans = max({(long long)0, sumLeft, sumRight, totalSum, sumLeft + sumRight});
        }
        cout << ans << endl;
        return 0;
    }
    const long long NEG_INF = LLONG_MIN / 2;
    vector<long long> f(k + 1, 0);
    vector<long long> g(k + 1, NEG_INF);

    for (int i = 1; i <= n; i++) {
        vector<long long> f_prev = f;
        for (int j = 1; j <= k; j++) {
            long long extend;
            if (g[j] == NEG_INF){
                extend = NEG_INF;
            } else {
                extend = g[j] + a[i];
            }
            long long start;
            if (f_prev[j-1] == NEG_INF) {
                    start = NEG_INF;
            } else {
                start = f_prev[j-1] + a[i];
                }
            g[j] = max(extend, start);
            f[j] = max(f_prev[j], g[j]);
        }
    }
    cout << f[k] << endl;
    return 0;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:55:31: error: 'LLONG_MIN' was not declared in this scope
   55 |     const long long NEG_INF = LLONG_MIN / 2;
      |                               ^~~~~~~~~
feast.cpp:4:1: note: 'LLONG_MIN' is defined in header '<climits>'; did you forget to '#include <climits>'?
    3 | #include <algorithm>
  +++ |+#include <climits>
    4 | using namespace std;