Submission #707397

#	Time	Username	Problem	Language	Result	Execution time	Memory
707397		safaricola	Bigger segments (IZhO19_segments)	C++17	13 / 100	1 ms	340 KiB

segments

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define rep(i,n) for(ll i = 1; i <= n; i++)
#define debug(x) cout<<#x<<' '<<x<<endl;
ll n, a[500010],kmin=LLONG_MAX,k[500010];
ii dp[500010];
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
    k[1]=1;
    rep(i,n)cin>>a[i];
	dp[1]={1,a[1]};
	ll K=1,ksum=0,kmsum=0,kmmin=LLONG_MAX;
	priority_queue<ii,vector<ii>, greater<ii> > pq,bg; // stores sum in current section needed to offset the value
	pq.push({a[1],0});
	bg.push({a[1],0});
	for(int i=2; i<=n; i++){
		//make a new group
		ksum+=a[i];
		kmsum+=a[i];
		while(!bg.empty()&&bg.top().f<=ksum){
			ii cur=bg.top();
			bg.pop();
			if(bg.empty()||bg.top().f>ksum){
				bg.push(cur);
				//debug(bg.top().f)debug(bg.top().s)  debug(ksum)debug(bg.top().f)debug(bg.top().s)  debug(ksum)
				kmin=min(kmin, ksum-bg.top().s);
				break;
			}
			kmin=min(kmin, ksum-cur.s);
		}
		if(kmin!=LLONG_MAX){
			while(!bg.empty()){
				bg.pop();
			}
			while(!pq.empty()){
				pq.pop();
			}
			kmsum=0;
			for(int j=k[K]; j<i; j++){
				if(j!=k[K])kmsum+=a[j];
				//cout<<"?";debug(kmsum)
				//cout<<"pushed "<<dp[j].s+kmsum<<endl;
				pq.push({dp[j].s+kmsum,kmsum});
			}
			kmsum+=a[i];
            K++;
            k[K]=i;
			dp[i]={K,kmin};
			ksum=0;
			bg.push({dp[i].s,0});
			kmin=kmmin=LLONG_MAX;
			//cout<<">>"<<i<<' '<<dp[i].f<<' '<<dp[i].s<<endl;
			continue;
		}
		// get min from K-1
		dp[i]={K,1e9};
		while(!pq.empty()&&pq.top().f<=kmsum){
			ii cur=pq.top();
			pq.pop();
			if(pq.empty()||pq.top().f>kmsum){
				pq.push(cur);
				//debug(kmsum)debug(pq.top().s)
				kmmin=min(kmmin, kmsum-pq.top().s);
				break;
			}
		}
		kmmin=LLONG_MAX;
		if(!pq.empty()&&pq.top().f<=kmsum){
			//debug(kmsum)debug(pq.top().s)
			kmmin=kmsum-pq.top().s;
		}
		// add on to K
		dp[i].s=min({dp[i-1].s+a[i],kmmin});
		bg.push({dp[i].s+ksum,ksum});
		//cout<<"pushed "<<dp[i].s+ksum<<endl;
		//cout<<'>'<<i<<' '<<dp[i].f<<' '<<dp[i].s<<endl;
	}
	cout<<K;
}

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