Submission #1099685

#TimeUsernameProblemLanguageResultExecution timeMemory
1099685Math4Life2020Rainy Markets (CCO22_day1problem2)C++17
25 / 25
560 ms152692 KiB
#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma") #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll,ll>; using vi = vector<ll>; int main() { ios_base::sync_with_stdio(false); cin.tie(0); ll N; cin >> N; ll B[N]; ll P[N-1]; ll U[N-1]; for (ll i=0;i<N;i++) { cin >> B[i]; } for (ll i=0;i<(N-1);i++) { cin >> P[i]; } for (ll i=0;i<(N-1);i++) { cin >> U[i]; } ll xc = 0; for (ll i=0;i<(N-1);i++) { xc = max(xc+P[i]-U[i]-B[i],0LL); if (xc>B[i+1]) { cout << "NO\n"; exit(0); } } cout << "YES\n"; ll x0[N]; ll xf[N]; ll v0[N]; ll zmin0[N]; ll zmax0[N]; ll vzmin0[N]; x0[0]=0; xf[0]=0; v0[0]=0; for (ll i=1;i<N;i++) { if (xf[i-1]+P[i-1]<=B[i-1]) { xf[i]=0; x0[i]=0; zmin0[i-1]=P[i-1]; zmax0[i-1]=P[i-1]; v0[i]=v0[i-1]; continue; } ll zmin = max(B[i-1]-xf[i-1],0LL); ll zmax = min(B[i-1]-x0[i-1],P[i-1]); assert(zmin<=zmax); ll xapp = min(xf[i-1],B[i-1]-zmin); ll vzmin = v0[i-1]+xf[i-1]-xapp; zmin0[i-1]=zmin; zmax0[i-1]=zmax; vzmin0[i-1]=vzmin; zmax = min(zmax+U[i-1],P[i-1]); x0[i]=P[i-1]-zmax; xf[i]=P[i-1]-zmin; v0[i]=vzmin; x0[i]=max(x0[i],0LL); if (xf[i]>B[i]) { ll D = xf[i]-B[i]; xf[i]-=D; v0[i]+=D; } } cout << v0[N-1]<<"\n"; ll ans0[N-1]; ll ans1[N-1]; ll ans2[N-1]; ll xfv = xf[N-1]; for (ll i=(N-2);i>=0;i--) { xfv = min(xfv,P[i]); ans2[i]=xfv; ll nleft=P[i]-xfv; ans0[i]=min(nleft,zmax0[i]); ans1[i]=nleft-ans0[i]; xfv=B[i]-ans0[i]; } for (int i=0;i<(N-1);i++) { cout << ans0[i] <<" "<<ans1[i] <<" "<<ans2[i]<<"\n"; } }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:29:5: warning: variable 'zmin0' set but not used [-Wunused-but-set-variable]
   29 |  ll zmin0[N]; ll zmax0[N]; ll vzmin0[N];
      |     ^~~~~
Main.cpp:29:31: warning: variable 'vzmin0' set but not used [-Wunused-but-set-variable]
   29 |  ll zmin0[N]; ll zmax0[N]; ll vzmin0[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...