Submission #343672

#	Time	Username	Problem	Language	Result	Execution time	Memory
343672		Tosic	Bigger segments (IZhO19_segments)	C++14	0 / 100	1 ms	384 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;
			while(prIdx < i and 1.0*a[prIdx+1] <= 1.0*(mid-1)*a[i]/(mid)){
				++prIdx;
			}
			while(prIdx > 0 and 1.0*a[prIdx] > 1.0*(mid-1)*a[i]/mid){
				--prIdx;
			}
			if(prMax[prIdx] >= mid-1){
				prMax[i] = max(prMax[i], mid); l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		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