제출 #1350882

#제출 시각아이디문제언어결과실행 시간메모리
1350882kokorooBikeparking (EGOI24_bikeparking)C++20
25 / 100
23 ms16824 KiB
#include<bits/stdc++.h>
//#include<atcoder/all>

using namespace std;
//using namespace atcoder;
#define rep(i,n) for(ll i=0; i<n; i++)
#define rrep(i,n) for(ll i=n-1; i>=0; i--)
#define print(a) cout<<a<<endl
typedef long long ll;
#define yn(flg) if(flg){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define YN(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define so(a) sort(a.begin(),a.end())
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define vs vector<string>
#define pb push_back
#define a2i(a,s) (ll)(a-s)
#define i2a(s,a) (char)(s+a)
#define ssize(a) a.size()
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<pair<ll,ll>,ll> P3;
typedef pair<pair<ll,ll>,pair<ll,ll>> P4;

typedef pair<ll, ll> Pll;
typedef pair<ll,Pll> Plll;
typedef pair<Pii, int> Piii;
const ll INF = 1000000000000000000;

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;

}
using ull=unsigned long long;






int main(){
//入力

	cin.tie(0);
	ios::sync_with_stdio(0);


	ll n;
	cin>>n;
	vector<ll> x(n);
	vector<ll> y(n);
	vector<ll> X(n);


	rep(i,n){
		cin>>x[i];
		X[i]=x[i];
	}
	rep(i,n)cin>>y[i];

//前計算
	if(n==2){
		ll ans2=0;
		ans2+=min(x[0],y[1]);
		ans2-=max((y[0]-max(x[0]-y[1],(ll)0)),(ll)0);
		cout<<ans2<<endl;
		return 0;
	}

//判定
	ll ans=0;
	ll p=n-1;
	vector<ll> v(n,0);
	vector<Pll> v2[300009];

	for(ll i=n-1;i>=0;i--){
		if(y[i]==0)continue;
		while(p>=0){
			if(p>=i){
				p--;
				continue;
			}
			if(y[i]>X[p]){
				ans+=X[p];
//				v2[p].push_back({i,X[p]});
				y[i]-=X[p];
				X[p]=0;
				p--;
			}else{
				ans+=y[i];
//				v2[p].push_back({i,y[i]});
				X[p]-=y[i];
				y[i]=0;
				break;
			}
		}

		v[i]=y[i];
//		ans-=v[i];
	}


	for(ll i=0;i<n;i++){
//		cout<<v[i]<<endl;
		if(v[i]>0){
			if(X[i]>0){
				v[i]=max((ll)0,v[i]-X[i]);
			}
			ans-=v[i];
//			if(v[i]>0){
//
//				sort(v2[i].begin(),v2[i].end());
//				for(ll j=0;j<v2[i].size();j++){
//					   ll nx=v2[i][j].first,cost=v2[i][j].second;
//					   if(cost>=v[i]){
//						   v[nx]+=v[i];
//						   ans-=v[i];
//						   v[i]=0;
//						   break;
//					   }else{
//						   v[nx]+=cost;
//						   ans-=v[i];
//						   v[i]-=cost;
//					   }
//				}

//				ans-=v[i];
//			}

		}
	}

	cout<<ans<<endl;





	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...