Submission #1200697

#TimeUsernameProblemLanguageResultExecution timeMemory
1200697_rain_Rainy Markets (CCO22_day1problem2)C++20
5 / 25
299 ms92568 KiB
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=(int)1e6; #define move asdasdasd LL t[N+2],tt[N+2],p[N+2],b[N+2],u[N+2],bb[N+2]={}; LL move[N+2],stay[N+2],buy[N+2]; int n; bool possible(LL need){ for(int i=1;i<=n;++i) bb[i]=b[i]; for(int i=1;i<n;++i) tt[i]=p[i],t[i]=u[i]; for(int i=n-1;i>=1;--i){ tt[i]-=min(tt[i],bb[i+1]); LL x; x=min(need,min(t[i],tt[i])); tt[i]-=x,need-=x; x=min(tt[i],bb[i]); tt[i]-=x,bb[i]-=x; if (tt[i]!=0) return false; } return true; } int main(){ ios::sync_with_stdio(false); cin.tie(0) ; cout.tie(0); // freopen("main.inp","r",stdin); // freopen("main.out","w",stdout); cin>>n; for(int i=1;i<=n;++i) cin>>b[i]; for(int i=1;i<n;++i) cin>>p[i]; for(int i=1;i<n;++i) cin>>u[i]; LL sum=0; for(int i=1;i<n;++i) sum+=u[i]; LL low=0,high=sum,ans=-1; while (low<=high){ LL mid=(low+high)/2; if (possible(mid)){ ans=mid; high=mid-1; } else low=mid+1; } if (ans==-1) { cout<<"NO"; return 0; } LL need=ans; for(int i=n-1;i>=1;--i){ move[i]=min(p[i],b[i+1]) , p[i]-=min(p[i],b[i+1]); LL x; x=min(need,p[i]); buy[i]=x,p[i]-=x,need-=x; x=min(p[i],b[i]); stay[i]=x,p[i]-=x,b[i]-=x; assert(p[i]==0); } cout<<"YES\n"; cout<<ans<<'\n'; for(int i=1;i<n;++i) cout<<stay[i]<<' '<<buy[i]<<' '<<move[i]<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...