Submission #1116457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116457		Hamed_Ghaffari	Feast (NOI19_feast)	C++17	100 / 100	146 ms	4684 KiB

feast

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

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using ull = unsigned long long;

#define X               first
#define Y               second
#define SZ(x)           int(x.size())
#define all(x)          x.begin(), x.end()
#define mins(a,b)       (a = min(a,b))
#define maxs(a,b)       (a = max(a,b))
#define pb              push_back
#define Mp              make_pair
#define lc              id<<1
#define rc              lc|1
// #define mid             ((l+r)/2)
mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());

const ll  INF = 1e9 + 23;
const ll  MOD = 1e9 + 7;
const int MXN = 3e5 + 5;
const int LOG = 23;

int n, k, a[MXN];

pll calc(ll lmb) {
    pll mx = Mp(0, 0), ans = mx;
    ll sum=0;
    for(int i=1; i<=n; i++) {
        sum += a[i];
        maxs(ans, Mp(mx.X+sum-lmb, mx.Y+1));
        maxs(mx, Mp(ans.X-sum, ans.Y));
    }
    return ans;
}

void Main() {
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> a[i];
    // ll l=-1, r=1e18;
    // while(r-l>1)
    //     (calc(mid).Y>=k ? l : r) = mid;
    // cout << calc(l).X + l*k << '\n';
    ll lo = 0;
	ll hi = 1e18;
	while (lo < hi) {
		ll mid = (lo + hi + 1) / 2;
		calc(mid).second >= k ? lo = mid : hi = mid - 1;
	}

	cout << calc(lo).first + lo * k << endl;
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int T = 1;
    // cin >> T;
    while(T--) Main();
    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