Submission #1285643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285643		Jawad_Akbar_JJ	Bigger segments (IZhO19_segments)	C++20	100 / 100	176 ms	16088 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];

signed main(){
	int n, Ans = 0;
	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] == 0)
			Mx[i] = 1, Sm[i] = pre[i];
		if (Mx[i-1] > Mx[i])
			Mx[i] = Mx[i-1], Sm[i] = Sm[i-1] + a[i];
		else if (Mx[i-1] == Mx[i])
			Sm[i] = min(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: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27