Submission #800256

#	Time	Username	Problem	Language	Result	Execution time	Memory
800256		vjudge1	Bigger segments (IZhO19_segments)	C++17	0 / 100	1 ms	212 KiB

segments

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

const int maxn = 5e5+3;
int n;
int a[maxn];
long long p[maxn];
int ans;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i=0; i<n; i++) cin >> a[i];

	p[0] = 0;
	for (int i=1; i<=n; i++) p[i] = p[i-1] + a[i-1];

	int l1 = 1, r1 = n;
	while (l1 <= r1) {
		int m1 = (l1+r1)/2;

		int cnt = 1, cur = n;
		for (int i=n-1; i>0 && cnt<m1; i--) {
			if (p[i] * (m1-cnt+1) <= p[cur] * (m1-cnt)) {
				cur = i;
				cnt++;
			}
		}

		if (cnt == m1) {
			ans = m1;
			l1 = m1 + 1;
		} else {
			r1 = m1 - 1;
		}
	}

	cout << ans << '\n';
	return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27