Submission #1254634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254634		dbence	Feast (NOI19_feast)	C++20	100 / 100	77 ms	2764 KiB

feast

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define len(x) (x).size()
#define lsb(x) (x) & (-x)
#define l(x) (x << 1) + 1
#define r(x) (x << 1) + 2
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;

template <typename T>
void print(T t) {
    cout << t << "\n";
}

template <typename T, typename... Args>
void print(T t, Args ...args) {
    cout << t << " ";
    print(args...);
}

const ll N = 3e5 + 1;
const ll inf = 1e14 + 1;
ll n, k, a[N];

pii calc(ll q) {
    ll pre = 0;
    pii opt = {0, 0}, mxm = opt;
    for (ll i = 1; i <= n; ++i) {
        pre += a[i];
        pii res = {opt.xx + pre + q, opt.yy - 1};
        mxm = max(mxm, res);
        opt = max(opt, {mxm.xx - pre, mxm.yy});
    }
    return {mxm.xx, -mxm.yy};
}

ll bin_search(ll l, ll r) {
    while (l < r) {
        ll q = l + r + 1 >> 1;
        if (calc(q).yy > k) {
            r = q - 1;
        } else {
            l = q;
        }
    }
    return l;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (ll i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    ll q = bin_search(-inf, 0);
    pii res = calc(q);
    cout << res.xx - q * k << "\n";
}

• 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