Submission #1285641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285641		Jawad_Akbar_JJ	Bigger segments (IZhO19_segments)	C++20	27 / 100	2 ms	580 KiB

segments

#include <iostream>
#include <algorithm>

using namespace std;
#define int long long
const int N = 1<<19;
int a[N], Sm[N], Mx[N], pre[N], n;

signed main(){
	cin>>n;

	for (int i=1;i<=n;i++)
		cin>>a[i], pre[i] = pre[i-1] + a[i];

	Mx[0] = 1;
	for (int i=1;i<=n;i++){
		if (Mx[i-1] > Mx[i])
			Mx[i] = Mx[i-1], Sm[i] = Sm[i-1] + a[i];

		int u = upper_bound(pre, pre + n + 1, pre[i] + Sm[i] - 1) - pre;
		if (Mx[u] < Mx[i] + 1)
			Mx[u] = Mx[i] + 1, Sm[u] = pre[u] - pre[i];
		else if (Mx[u] == Mx[i] + 1)
			Sm[u] = min(Sm[u], pre[u] - pre[i]);
	}
	cout<<Mx[n]<<'\n';
}

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