Submission #1173112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173112		yegorvk	Feast (NOI19_feast)	C++20	100 / 100	71 ms	2632 KiB

feast

#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#endif

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll k, n;
vector<ll> a;

struct state {
    ll ans;
    int cnt;

    bool operator<(const state &s) const {
        return make_pair(ans, cnt) < make_pair(s.ans, s.cnt);
    }

    state operator+(ll v) const {
        return {ans+v, cnt};
    }

    state operator+(pair<ll, int> v) const {
        return {ans+v.first, cnt+v.second};
    }

    ll comp(ll p) {
        return ans + p * cnt;
    }
};

state test(ll cost) {
    state dp_old[2], dp_new[2];

    dp_old[0] = {0, 0};
    dp_old[1] = {a[0] - cost, 1};

    for (int i = 1; i < n; ++i) {
        dp_new[0] = max(dp_old[0], dp_old[1]);
        dp_new[1] = max(dp_old[1] + a[i], dp_old[0] + make_pair(a[i] - cost, 1));
        swap(dp_old, dp_new);
    }

    return max(dp_old[0], dp_old[1]);
}

void solve() {
    cin >> n >> k;

    a.resize(n);

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

    ll l = 0, r = 1e14;
    ll ans = 0;
    int c;

    while (r - l > 1) {
        ll m = (l + r) / 2;
        auto s = test(m);
        c = s.cnt;
        if (c >= k)
            l = m;
        else
            r = m - 1;
    }

    ans = max(test(l).comp(l), test(r).comp(r));

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);

    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    // ll t;
    // cin >> t;
    //
    // while (t--) solve();

    return 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