Submission #1210879

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

feast

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

using namespace std;

typedef pair<int, int> ii;

int n, k;
vector<int> a;

ii maxsub(int c) {
	int n = a.size();
	int t = 0, cnt = 0;
	int cur = 0;
	for (int 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};
}

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

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

	int l = -1e10, h = 1e10;
	int ans = 0;
	while (l <= h) {
		int mid = (l + h) / 2;
		ii res = maxsub(mid);
		int total = res.fi;
		int 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