Submission #1210880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210880		virgonius	Feast (NOI19_feast)	C++20	18 / 100	31 ms	2632 KiB

feast

#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl "\n"
#define fi first
#define se second
#define ll long long

using namespace std;

typedef pair<ll, ll> ii;

ll n, k;
vector<ll> a;

ii maxsub(ll c) {
	ll t = 0, cnt = 0;
	ll cur = 0;
	for (ll i = 0; i < n; ++i) {
		if (cur + a[i] - c < 0) {
			cur = 0;
		} else {
			cur += a[i] - c;
			if (cur >= 0) {
				t += cur;
				cnt++;
				cur = 0;
			}
		}
	}
	return {t + cnt * c, cnt};
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k;
	a.resize(n);
	
	for (ll i = 0; i < n; ++i) {
		cin >> a[i];
	}

	if (k == 1) {
		ll cur = a[0], res = a[0];
		for (ll i = 1; i < n; ++i) {
			cur = max(a[i], cur + a[i]);
			res = max(res, cur);
		}
		cout << res << endl;
		return 0;
	}

	ll l = -1e10, h = 1e10;
	ll ans = 0;
	while (l <= h) {
		ll mid = (l + h) / 2;
		ii res = maxsub(mid);
		ll total = res.fi;
		ll num = res.se;
		if (num >= k) {
			ans = total - mid * k;
			l = mid + 1;
		} else {
			h = mid - 1;
		}
	}
	cout << ans << endl;
	return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 18 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29