//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<<#x<<" is ";for(auto p:x)cerr<<p.first<<" "<<p.second<<endl;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)
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';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |