Submission #265520

#	Time	Username	Problem	Language	Result	Execution time	Memory
265520		Segtree	Bigger segments (IZhO19_segments)	C++14	37 / 100	650 ms	71356 KiB

segments

#include<iostream>
#include<algorithm>
#include<vector>
#include<fstream>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define N 3010
ll n,a[N],s[N];
ll dp[N][N];
int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin>>n;
	rep(i,n)cin>>a[i];
	s[0]=0;
	rep(i,n)s[i+1]=s[i]+a[i];
	rep(i,n+1)dp[i][0]=1e18;
	dp[0][0]=0;
	for(int k=1;k<=n;k++){
		vector<ll> score,place;
		//scoreは単調増加
		for(int i=0;i<=n;i++){
			ll l=-1,r=score.size(),mid;
			while(l<r-1){
				mid=(l+r)>>1;
				if(s[i]>=score[mid])l=mid;
				else r=mid;
			}
			if(l>=0){
				dp[i][k]=s[i]-s[place[l]];
			}
			else dp[i][k]=1e18;
			ll sc=dp[i][k-1]+s[i];
			while(score.size()>0){
				if(score.back()>=sc){
					score.pop_back();
					place.pop_back();
				}
				else break;
			}
			score.push_back(sc);
			place.push_back(i);
		}
	}
	ll ans=1;
	for(int k=1;k<=n;k++){
		if(dp[n][k]<1e18)ans=k;
	}
	cout<<ans<<endl;
}

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