Submission #800135

#	Time	Username	Problem	Language	Result	Execution time	Memory
800135		vjudge1	Bigger segments (IZhO19_segments)	C++17	0 / 100	1 ms	340 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;
		while (cnt < m1 && m1 - cnt <= cur - 1) {
			int l2 = m1 - cnt, r2 = cur - 1, nxt = 0;
			while (l2 <= r2) {
				int m2 = (l2+r2)/2;
				if (p[m2] * (m1-cnt+1) <= p[cur] * (m1-cnt)) {
					nxt = m2;
					l2 = m2 + 1;
				} else {
					r2 = m2 - 1;
				}
			}
			cur = nxt;
			if (nxt != 0) 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