Submission #482209

#	Time	Username	Problem	Language	Result	Execution time	Memory
482209		luka1234	Bigger segments (IZhO19_segments)	C++14	27 / 100	1584 ms	153268 KiB

segments

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
int a[3001];
ll p[3001];
set<pair<ll,ll> > s[3001];
ll d[3001][3001];
int n;
int main(){
	cin>>n;
	for(int k=1;k<=n;k++){
		cin>>a[k];
		p[k]=p[k-1]+a[k];
	}
	d[0][0]=0;
	s[0].insert({0,0});
	set<pair<ll,ll> >::iterator it;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			it=s[j-1].lower_bound({p[i]+1,0});
			if(it==s[j-1].begin()){
				d[i][j]=1e18;
				continue;
			}
			it--;
			int ind=(*it).ss;
			d[i][j]=p[i]-p[ind];
			ll v=d[i][j]+p[i];
			while(!s[j].empty()&&(*s[j].rbegin()).ff>=v){
				s[j].erase(*s[j].rbegin());
			}
			s[j].insert({v,i});
		}
	}
	for(int j=n;j>=1;j--){
		if(d[n][j]!=1e18){
			cout<<j;
			return 0;
		}
	}
    return 0;
}

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