Submission #343702

#	Time	Username	Problem	Language	Result	Execution time	Memory
343702		Tosic	Bigger segments (IZhO19_segments)	C++14	0 / 100	1 ms	364 KiB

segments

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

int n, prMax[maxn];
long long a[maxn];

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
		a[i] += a[i-1];
	}
	for(int i = 1; i <= n; ++i){
		int l = 1, r = n, prIdx = 0;
		while(l <= r){
			int mid = (l + r)/2;
			prIdx = upper_bound(a, a+1+n, (1.0*((mid-1)*a[i])) /mid)-a-1;
			if(prMax[prIdx] >= mid-1){
				prMax[i] = max(prMax[i], mid); l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		prIdx = upper_bound(a, a+n+1, ((r-1)*a[i])/r)-a-1;
		if(r){
			if(prIdx >= 0 and prMax[prIdx] >= r-1){
				prMax[i] = max(prMax[i], r);
			}
		}
		if(l){
			prIdx = upper_bound(a, a+n+1, ((l-1)*a[i])/l)-a-1;
			if(prIdx >= 0 and prMax[prIdx] >= l-1){
				prMax[i] = max(prMax[i], l);
			}	
		}
		
		prMax[i] = max(prMax[i-1], prMax[i]);
	}
	cout << prMax[n];
}

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