Submission #1211287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211287		malta	Feast (NOI19_feast)	C++20	18 / 100	80 ms	2632 KiB

feast

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const __int128 INF = (__int128)4e18;

int N, K;
vector<ll> A;

// returns {best_value_with_penalties, segment_count}
pair<__int128,int> solve(__int128 m){
    __int128 dp0 = 0, dp1 = -INF;
    int c0 = 0, c1 = 0;
    for(int i = 0; i < N; i++){
        __int128 x = A[i];
        __int128 t1 = dp1 + x;
        int tc1 = c1;
        __int128 t2 = dp0 + x - m;
        int tc2 = c0 + 1;
        __int128 ndp1; int nc1;
        if(t1 >= t2){ ndp1 = t1; nc1 = tc1; }
        else       { ndp1 = t2; nc1 = tc2; }

        __int128 ndp0; int nc0;
        if(dp0 >= dp1){ ndp0 = dp0; nc0 = c0; }
        else          { ndp0 = dp1; nc0 = c1; }

        dp1 = ndp1; c1 = nc1;
        dp0 = ndp0; c0 = nc0;
    }
    if(dp0 >= dp1) return {dp0, c0};
    else           return {dp1, c1};
}

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

    cin >> N >> K;
    A.resize(N);
    for(int i = 0; i < N; i++) cin >> A[i];

    __int128 lo = -(__int128)1e15, hi = (__int128)1e15, best = hi;
    while(lo <= hi){
        __int128 mid = (lo + hi) >> 1;
        auto [val, cnt] = solve(mid);
        if(cnt <= K){
            best = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }

    auto [val, cnt] = solve(best);
    __int128 ans = val + best * K;
    cout << (ll)ans << "\n";
    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