Submission #467054

#	Time	Username	Problem	Language	Result	Execution time	Memory
467054		mosiashvililuka	Bigger segments (IZhO19_segments)	C++14	100 / 100	159 ms	48200 KiB

segments

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,dp[500009],dp2[500009],f[500009],jm[500009],lef,rig,mid;
vector <long long> v[500009];
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(i=1; i<=a; i++){
		cin>>f[i];jm[i]=jm[i-1]+f[i];
	}
	for(i=1; i<=a; i++){
		dp[i]=1;dp2[i]=jm[i];
		for(vector <long long>::iterator it=v[i].begin(); it!=v[i].end(); it++){
			/*if(dp[i]<dp[(*it)]+1||(dp[i]==dp[(*it)]+1&&dp2[i]>jm[i]-jm[(*it)])){
				dp[i]=dp[(*it)]+1;dp2[i]=jm[i]-jm[(*it)];
			}*/
			jj=max((*it),jj);
		}
		if(jj!=0){
			if(dp[i]<dp[jj]+1||(dp[i]==dp[jj]+1&&dp2[i]>jm[i]-jm[jj])){
				dp[i]=dp[jj]+1;dp2[i]=jm[i]-jm[jj];
			}
		}
		/*for(j=i-1; j>=1; j--){
			if(dp2[j]+jm[j]<=jm[i]){
				dp[i]=dp[j]+1;dp2[i]=jm[i]-jm[j];
				break;
			}
		}*/
		lef=0;rig=a+1;
		while(1){
			if(lef+1>=rig) break;
			mid=(lef+rig)/2;
			if(dp2[i]+jm[i]<=jm[mid]){
				rig=mid;
			}else{
				lef=mid;
			}
		}
		v[rig].push_back(i);
	}
	cout<<dp[a];
	return 0;
}

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