Submission #1147763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147763		spydukc	Feast (NOI19_feast)	C++20	4 / 100	130 ms	12136 KiB

feast

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define int long long
using namespace std;

int a[300001];

pair<int, int> solve(int l, int n) {
    pair<int, int> dp[n][2];
        dp[0][0] = {0, 0};
        dp[0][1] = {a[0]-l, 1};
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = max(
                mp(dp[i-1][0].f+a[i]-l, dp[i-1][0].s+1),
                mp(dp[i-1][1].f+a[i], dp[i-1][0].s)
            );
        }
        return max(dp[n-1][0], dp[n-1][1]);
}

signed main() {
	int n, k; cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int low = 0;
    int high = 1e9;
    int mid = low + (high - low) / 2;
    while (low < high) {
        mid = low + (high - low) / 2;
        pair<int, int> res = solve(mid, n);
        if (res.s <= k) {
            high = mid;
        }
        else {
            low = mid + 1;
        }
    }
    cout << solve(low, n).f+low*k;
}

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