Submission #1139914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139914		minhnguyent546	Feast (NOI19_feast)	C++20	41 / 100	1096 ms	7232 KiB

feast

/**            
 * author      minhnguyent546
 * created_at  Sun, 2025-01-26 08:09:26
 * problem     https://oj.uz/problem/view/NOI19_feast
 **/           
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "cp/debug.h"
#else
#define debug(...)
#define cerr if (false) cerr
#endif

int n, k;
vector<int> arr;
vector<long long> pref;
void read() {
    cin >> n >> k;
    arr.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    pref.resize(n + 1);
    for (int i = 0; i < n; ++i) {
        pref[i + 1] = pref[i] + arr[i];
    }
}

long long sum(int l, int r) {
    assert(0 <= l && l <= r && r < n);
    return pref[r + 1] - pref[l];
}


const long long INF_LL = 0x3f3f3f3f3f3f3f3f;

namespace brute {
bool check() {
    return n <= 300;
}
void solve() {
    cerr << " *** [BRUTE] *** " << '\n';

    vector<long long> dp(n + 1, -INF_LL);
    vector<long long> ndp(n + 1);
    dp[0] = 0;
    for (int j = 0; j <= k; ++j) {
        for (int i = 1; i <= n; ++i) {
            ndp[i] = ndp[i - 1];
            if (j > 0) {
                for (int z = 0; z < i; ++z) {
                    ndp[i] = max(ndp[i], dp[z] + max(0LL, sum(z, i - 1)));
                }
            }
        }
        dp.swap(ndp);
    }
    cout << dp[n] << '\n';

}
} // namespace brute

namespace sub7 {
bool check() {
    return true;
}
void solve() {
    cerr << " *** [SUB 7] *** " << '\n';
    long long low = -(long long) 1e18, high = 0;

    vector<long long> dp(n + 1);
    vector<int> min_seg(n + 1);
    auto gud = [&](long long lambda) -> bool {
        fill(dp.begin(), dp.end(), -INF_LL);
        dp[0] = 0;
        min_seg[0] = 0;
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1];
            min_seg[i] = min_seg[i - 1];
            for (int z = 0; z < i; ++z) {
                long long cost = sum(z, i - 1) + lambda;
                long long nval = dp[z] + cost;
                if (nval > dp[i]) {
                    dp[i] = nval;
                    min_seg[i] = min_seg[z] + 1;
                } else if (nval == dp[i]) {
                    min_seg[i] = min(min_seg[i], min_seg[z] + 1);
                }
            }
        }
        // cerr << "lambda = " << lambda << ", min_seg[n] = " << min_seg[n] << ", dp[n] = " << dp[n] << '\n';
        return min_seg[n] <= k;
    };
    while (low < high) {
        long long mid = low + (high - low + 1) / 2;
        if (gud(mid)) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    long long lambda = high;
    gud(lambda);
    long long ans = dp[n] - lambda * k;
    cout << ans << '\n';
}
} // namespace sub7


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    read();

    #ifdef LOCAL
        sub7::solve(); return 0;
        brute::solve(); return 0;
    #endif

    if (brute::check()) {
        brute::solve(); return 0;
    }

    if (sub7::check()) {
        sub7::solve(); return 0;
    }

    assert(false);
    
    return 0;
}

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