제출 #1340300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1340300		emv	Feast (NOI19_feast)	C++20	큐에 대기중	0 ms	0 KiB

feast

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

#define int long long

int n;
vector<int> a;

pair<int, int> check(const int lmb) {
    vector<vector<pair<int, int>>> dp(n, vector<pair<int, int>> (2));
    dp[0] = {{0, 0}, {a[0] - lmb, 0}};
    for (int i = 1; i < n; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = max(pair(dp[i - 1][0].first + a[i] - lmb, dp[i - 1][0].second + 1),
                       pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second));
    }
    return max(dp[n - 1][0], dp[n - 1][1]);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifdef LOCAL
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    int k; cin >> n >> k;
    a.resize(n);
    for (int &x: a)
        cin >> x;
    int l = -1, r = 2e14;
    while (r - l > 1) {
        int m = (l + r) / 2;
        (check(m).second <= k ? r : l) = m;
    }

    cout << check(r).first + check(r).second * r << '\n';
}