제출 #1309157

#제출 시각아이디문제언어결과실행 시간메모리
1309157goduadzesabaBigger segments (IZhO19_segments)C++20
100 / 100
68 ms15956 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5,mod=998244353,inf=1e18;
int _t,n; vector <int> p(N,0); pair<int,int> dp[N];
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for (int i=1; i<=n; i++) cin>>p[i],p[i]+=p[i-1];
	for (int i=0; i<=n; i++) dp[i]={1,0};
	for (int i=1; i<=n; i++){
		dp[i]=max(dp[i],dp[i-1]);
		int x=lower_bound(p.begin(),p.begin()+n+1,2*p[i]-p[dp[i].second])-p.begin();
		if (x<=n) dp[x]=max(dp[x],{dp[i].first+1,i});
	//	cout<<x<<" "<<dp[i].first<<" "<<dp[i].second<<"\n";
	} cout<<dp[n].first<<"\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...