제출 #1285643

#제출 시각아이디문제언어결과실행 시간메모리
1285643Jawad_Akbar_JJBigger segments (IZhO19_segments)C++20
100 / 100
176 ms16088 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...