Submission #1137585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137585		anmattroi	Feast (NOI19_feast)	C++20	100 / 100	123 ms	11004 KiB

feast

#include<bits/stdc++.h>
#define maxn 300005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
using li = pair<int64_t, int>;

int n, k;
int a[maxn];

li dp[maxn][2];

li solve_lambda(int64_t x) {
    dp[0][1] = {LLONG_MIN/2, 0};

    for (int i = 1; i <= n; i++) {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
        dp[i][1] = max(li{dp[i-1][1].fi+a[i], dp[i-1][1].se}, li{dp[i-1][0].fi+a[i]-x, dp[i-1][0].se+1});
    }

    return max(dp[n][0], dp[n][1]);
}

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

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

    int64_t lo = 0, hi = 100000000000000000LL;
    while (hi-lo>1) {
        int64_t mid = (lo+hi)>>1LL;
        if (solve_lambda(mid).se >= k) lo = mid;
        else hi = mid;
    }
    cout << solve_lambda(lo).fi + k*lo;
}

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