Submission #420044

#	Time	Username	Problem	Language	Result	Execution time	Memory
420044		CrouchingDragon	Feast (NOI19_feast)	C++17	100 / 100	129 ms	2756 KiB

feast

#include "bits/stdc++.h"

using namespace std;

#define endl '\n'
#define debug(x) cerr << #x << " == " << (x) << '\n';
#define all(x) begin(x), end(x)

using ll = long long;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

template<typename T>
bool chmin(T& x, T y) { return y < x ? (x = y, true) : false; }
template<typename T>
bool chmax(T& x, T y) { return x < y ? (x = y, true) : false; }
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

    vector<int> A(N);
    for (auto& x : A) cin >> x;

    auto f = [&](ll z) {
        ll dpmax = 0, prefsum = 0, prefmax = 0;
        int cnt_dpmax = 0, cnt_prefmax = 0;
        for (auto x : A) {
            prefsum += x;
            ll dp = prefsum + prefmax - z;
            if (chmax(dpmax, dp)) cnt_dpmax = 1 + cnt_prefmax;
            if (chmax(prefmax, dpmax - prefsum)) cnt_prefmax = cnt_dpmax;
        }
        return pair(dpmax, cnt_dpmax);
    };

    const ll inf = 1e13;
    ll L = 0, R = inf;
    while (L < R) {
        ll M = L + (R - L) / 2;
        f(M).second <= K ? R = M : L = M + 1;
    }

    auto [a, b] = f(L);
    ll ans = a + K * L;
    cout << ans << endl;

    exit(0);
}

• 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