oj.uz

Submission #1099683

# Submission time Handle Problem Language Result Execution time Memory
1099683 2024-10-12T02:45:52 Z Math4Life2020 Rainy Markets (CCO22_day1problem2) C++17
0 / 25
 180 ms 23916 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 150 ms 23916 KB Output is correct
5 Correct 180 ms 23896 KB Output is correct
6 Correct 155 ms 23900 KB Output is correct
7 Correct 172 ms 23900 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Runtime error 2 ms 1116 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Runtime error 0 ms 604 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Runtime error 0 ms 604 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 150 ms 23916 KB Output is correct
5 Correct 180 ms 23896 KB Output is correct
6 Correct 155 ms 23900 KB Output is correct
7 Correct 172 ms 23900 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Runtime error 2 ms 1116 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -