Submission #343672

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
343672	2021-01-04T11:18:14 Z	Tosic	Bigger segments (IZhO19_segments)	C++14	0 / 100	1 ms	384 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	376 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Incorrect	1 ms	364 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #2

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	376 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Incorrect	1 ms	364 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	376 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Incorrect	1 ms	364 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #4

0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	376 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Incorrect	1 ms	364 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #5

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	376 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Incorrect	1 ms	364 KB	Output isn't correct
7	Halted	0 ms	0 KB	-