Submission #1099683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099683		Math4Life2020	Rainy Markets (CCO22_day1problem2)	C++17	0 / 25	180 ms	23916 KiB

Main

#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;
			v0[i]=v0[i-1];
		}
		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];
      |                               ^~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 9