Submission #1135240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135240		hamzabc	Bigger segments (IZhO19_segments)	C++20	100 / 100	49 ms	16052 KiB

segments

#include <bits/stdc++.h>
 
 
using namespace std;
 
 
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'


long long int N;


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	vector<long long int> lst(N), p(N, -1), out(N);
	long long int *prefix = new long long int[N + 1];
	prefix[0] = 0;
	prefix++;
	for (int i = 0; i < N; i++){
		cin >> lst[i];
		prefix[i] = lst[i];
		prefix[i] += prefix[i - 1];
	}
	for (int i = 0; i < N; i++){
		auto k = lower_bound(prefix + i, prefix + N, prefix[i] * 2 - prefix[p[i]]);
		if (k != prefix + N){
			p[k - prefix] = i;
			out[k - prefix] = out[i] + 1;
		}
		if (i != N - 1){
			if (out[i] > out[i + 1]){
				p[i + 1] = p[i];
				out[i + 1] = out[i];
			}else{
				p[i + 1] = max(p[i + 1], p[i]);
			}
		}
	}
	cout << out[N - 1] + 1;
	return 0;
}

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