Submission #1254584

#TimeUsernameProblemLanguageResultExecution timeMemory
1254584dbenceFeast (NOI19_feast)C++20
12 / 100
79 ms2632 KiB
#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 = 1e9 + 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]; opt = max(opt, {mxm.xx - pre, mxm.yy}); 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; if (calc(q).yy < k) { l = q + 1; } else { r = 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, inf); pii res = calc(q); cout << res.xx - q * res.yy << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...