Submission #1211309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211309		malta	Feast (NOI19_feast)	C++20	18 / 100	41 ms	2780 KiB

feast

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

typedef long long ll;

tuple<ll, int, int> solve(ll lam, vector<ll> &a) {
    int n = a.size();
    if (n == 0) 
        return make_tuple(0, 0, 0);

    ll dp0_val = 0;
    int dp0_min = 0, dp0_max = 0;

    ll dp1_val = a[0] - lam;
    int dp1_min = 1, dp1_max = 1;

    for (int i = 1; i < n; i++) {
        ll prev0_val = dp0_val;
        ll prev1_val = dp1_val;
        int prev0_min = dp0_min, prev0_max = dp0_max;
        int prev1_min = dp1_min, prev1_max = dp1_max;

        if (prev0_val > prev1_val) {
            dp0_val = prev0_val;
            dp0_min = prev0_min;
            dp0_max = prev0_max;
        } else if (prev0_val < prev1_val) {
            dp0_val = prev1_val;
            dp0_min = prev1_min;
            dp0_max = prev1_max;
        } else {
            dp0_val = prev0_val;
            dp0_min = min(prev0_min, prev1_min);
            dp0_max = max(prev0_max, prev1_max);
        }

        ll option1_val = prev0_val + a[i] - lam;
        int option1_min = prev0_min + 1;
        int option1_max = prev0_max + 1;

        ll option2_val = prev1_val + a[i];
        int option2_min = prev1_min;
        int option2_max = prev1_max;

        if (option1_val > option2_val) {
            dp1_val = option1_val;
            dp1_min = option1_min;
            dp1_max = option1_max;
        } else if (option1_val < option2_val) {
            dp1_val = option2_val;
            dp1_min = option2_min;
            dp1_max = option2_max;
        } else {
            dp1_val = option1_val;
            dp1_min = min(option1_min, option2_min);
            dp1_max = max(option1_max, option2_max);
        }
    }

    ll res_val;
    int res_min, res_max;
    if (dp0_val > dp1_val) {
        res_val = dp0_val;
        res_min = dp0_min;
        res_max = dp0_max;
    } else if (dp0_val < dp1_val) {
        res_val = dp1_val;
        res_min = dp1_min;
        res_max = dp1_max;
    } else {
        res_val = dp0_val;
        res_min = min(dp0_min, dp1_min);
        res_max = max(dp0_max, dp1_max);
    }

    return make_tuple(res_val, res_min, res_max);
}

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

    int N, K;
    cin >> N >> K;

    vector<ll> A(N);
    int count_positive = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        if (A[i] > 0) 
            count_positive++;
    }

    int K0 = min(K, count_positive);
    if (K0 == 0) {
        cout << 0 << endl;
        return 0;
    }

    ll low = -3e14;
    ll high = 3e14;
    ll ans_seg = -1e18;
    bool found = false;

    while (low <= high) {
        ll lam = (low + high) / 2;
        auto [val, cmin, cmax] = solve(lam, A);

        if (cmax < K0) {
            high = lam - 1;
        } else if (cmin > K0) {
            low = lam + 1;
        } else {
            ans_seg = val + lam * K0;
            found = true;
            break;
        }
    }

    if (found) {
        ll ans = max(0LL, ans_seg);
        cout << ans << endl;
    } else {
        auto [val_low, cmin_low, cmax_low] = solve(low, A);
        ll candidate_low = -1e18;
        if (cmin_low <= K0 && K0 <= cmax_low) {
            candidate_low = val_low + low * K0;
        } else {
            int k1 = max(cmin_low, 0);
            int k2 = min(cmax_low, K0);
            candidate_low = max(val_low + low * k1, val_low + low * k2);
        }

        auto [val_high, cmin_high, cmax_high] = solve(high, A);
        ll candidate_high = -1e18;
        if (cmin_high <= K0 && K0 <= cmax_high) {
            candidate_high = val_high + high * K0;
        } else {
            int k1 = max(cmin_high, 0);
            int k2 = min(cmax_high, K0);
            candidate_high = max(val_high + high * k1, val_high + high * k2);
        }

        ll ans = max(0LL, max(candidate_low, candidate_high));
        cout << ans << endl;
    }

    return 0;
}

• Subtask 1: 0 / 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