Submission #1224941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224941		shoeib	Feast (NOI19_feast)	C++20	0 / 100	187 ms	8516 KiB

feast

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

using ll = long long;
using db = double;

const int MAXN = 300005;
const db EPS = 1e-6;

ll n, k;
vector<ll> a, pre;
db dp[MAXN];
int opt[MAXN]; // 0 = skip, 1 = take segment

pair<ll, ll> slv(db mid) {
    dp[0] = 0;
    opt[0] = 0;
    pair<db, ll> best = {0, 0}; // (dp[j] - pre[j], count)

    for (ll i = 1; i <= n; ++i) {
        db take_val = best.first + pre[i] - mid;
        ll take_cnt = best.second + 1;

        if (dp[i - 1] > take_val) {
            dp[i] = dp[i - 1];
            opt[i] = 0;
        } else {
            dp[i] = take_val;
            opt[i] = 1;
        }

        db candidate_val = dp[i] - pre[i];
        ll candidate_cnt = (opt[i] == 1 ? take_cnt : best.second);

        if (make_pair(candidate_val, candidate_cnt) > best) {
            best = {candidate_val, candidate_cnt};
        }
    }

    // Count segments
    ll seg_cnt = 0;
    for (ll i = n; i >= 1; --i) {
        if (opt[i] == 1) {
            seg_cnt++;
            while (i > 0 && opt[i] == 1 && dp[i] - pre[i] == dp[i - 1] - pre[i - 1]) i--;
        }
    }

    return {seg_cnt, 0};
}

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

    cin >> n >> k;
    a.resize(n + 1);
    pre.assign(n + 1, 0);

    for (ll i = 1; i <= n; ++i) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }

    db lo = 0, hi = 1e6;
    for (int it = 0; it < 40; ++it) {
        db mid = (lo + hi) / 2;
        auto [cnt, _] = slv(mid);
        if (cnt > k) lo = mid + EPS;
        else hi = mid;
    }

    slv(hi);
    cout << dp[n] + hi * k << "\n";

    return 0;
}

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