Submission #1215357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215357		akqxolotl	Bikeparking (EGOI24_bikeparking)	C++20	100 / 100	31 ms	7704 KiB

Main

//Segment Tree is a State of Mind
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define debugl(x) cerr <<'\n'<< #x << " is "; for(auto p : x) cerr << p << " "; cerr << endl;
#define debugpl(x) cerr<<"---\n";cerr<<#x<<" is:\n";for(auto p:x)cerr<<p.first<<" "<<p.second<<endl;cerr<<"---\n";cerr<<endl;
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)(x).size()
	
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	//mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
	int n;cin>>n;
	deque<pii> dq;
	vi v(n);
	int ts=0;
	for(int i=0;i<n;i++){
		int x;cin>>x;
		ts+=x;
		if(x)dq.pb({x,i});
	}
	for(int i=0;i<n;i++){
		int x;cin>>x;
		ts-=x;
		v[i]=x;
	}
	while(ts>0){
		if(ts>=dq.back().fi){
			ts-=dq.back().fi;
			dq.pop_back();
		}else{
			dq.back().fi-=ts;
			ts=0;
		}
	}
	int nc=0,s=0,tnc=0;
	for(int i=0;i<n;i++){
		//debugpl(dq)
		//debug(i)
		//debug(nc)
		tnc=0;
		while(v[i]>0){
			while(dq[0].fi<=0)dq.pop_front();
			while(dq.back().fi<=0)dq.pop_back();
			if(dq[0].se<i){
				int t=min(dq[0].fi,v[i]);
				s+=t;
				v[i]-=t;
				dq[0].fi-=t;
			}else{
				if(nc>0){
					int t=min(nc,v[i]);
					nc-=t;
					v[i]-=t;
					while(t>0){
						if(t>=dq.back().fi){
							t-=dq.back().fi;
							dq.pop_back();
						}else{
							dq.back().fi-=t;
							t=0;
						}
					}
				}else{
					if(dq[0].se==i){
						int t=min(dq[0].fi,v[i]);
						tnc+=t;
						v[i]-=t;
						dq[0].fi-=t;
					}else{
						int t=min(dq.back().fi,v[i]);
						//debug(s)
						s-=t;
						//debug(s)
						v[i]-=t;
						dq.back().fi-=t;
					}
				}
			}
		}
		nc+=tnc;
		
	}
	cout<<s<<'\n';
}

• Subtask 1: 16 / 16
• Subtask 2: 9 / 9
• Subtask 3: 19 / 19
• Subtask 4: 24 / 24
• Subtask 5: 32 / 32