Submission #1293473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293473		haha	Feast (NOI19_feast)	C++20	22 / 100	1096 ms	11952 KiB

feast

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

#define ll long long
const ll INF = (ll)4e18;
const int maxn = 300000 + 5;

int n, k;
ll a[maxn], sum[maxn];
ll dp[maxn], newdp[maxn], best[maxn];

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

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];
    }

    int neg = 0, pos = 0;
    for (int i = 1; i <= n; i++){
        if (a[i] < 0) neg++;
        else pos++;
    }

    if (pos == n) { cout << sum[n]; return 0; }
    if (neg == n) { cout << 0; return 0; }

    // K = 1 → bài max subarray
    if (k == 1) {
        ll ans = -INF, mn = 0;
        for (int i = 1; i <= n; i++) {
            ans = max(ans, sum[i] - mn);
            mn = min(mn, sum[i]);
        }
        cout << ans;
        return 0;
    }

    // DP cho K > 1
    for (int i = 0; i <= n; i++) dp[i] = -INF;
    dp[0] = 0;

    ll ans = 0;

    for (int j = 1; j <= k; j++) {

        best[0] = dp[0] - sum[0];
        for (int i = 1; i <= n; i++)
            best[i] = max(best[i-1], dp[i] - sum[i]);

        newdp[0] = 0; // đoạn có thể rỗng

        for (int i = 1; i <= n; i++) {
            newdp[i] = max(newdp[i-1], best[i-1] + sum[i]);
            if (j == k) ans = max(ans, newdp[i]);
        }

        // chuyển sang vòng kế tiếp
        for (int i = 0; i <= n; i++)
            dp[i] = newdp[i];
    }

    cout << ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 18 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29