Submission #1163195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163195		WH8	Rainy Markets (CCO22_day1problem2)	C++20	25 / 25	1491 ms	108068 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)

#define pb push_back
#define int long long 
#define f first
#define s second
#define pll pair<long long, long long>

signed main(){
	int n;cin>>n;
	vector<int> sc(n,0), p(n-1,0), op(n-1,0), uc(n-1, 0), sp(n, 0), up(n-1, 0);
	for(int i=0;i<n;i++)cin>>sc[i];
	for(int i=0;i<n-1;i++){ 
		cin>>p[i];
		op[i]=p[i];
	}
	for(int i=0;i<n-1;i++)cin>>uc[i];
	for(int i=0;i<n-1;i++){
		int l=min(sc[i]-sp[i],p[i]);
		sp[i]+=l;
		p[i]-=l;
		int m=min(uc[i]-up[i],p[i]);
		up[i]+=m;
		p[i]-=m;
		int r=min(sc[i+1]-sp[i+1],p[i]);
		sp[i+1]+=r;
		p[i]-=r;
		if(p[i]>0){
			cout<<"NO";
			return 0;
		}
	}
	//~ for (int i=0;i<n;i++){
		//~ cout<<sp[i]<<" ";
	//~ }
	//~ cout<<endl;
	int le[n];fill(le,le+n,0);
	for(int i=n-2;i>=0;i--){
		int m=min(sc[i+1]-sp[i+1], up[i]);
		sp[i+1]+=m;
		up[i]-=m;
		// you cant pull people from market i-1 to go to shelter i+1!
		
		int l=min(op[i]-(up[i]+(sp[i+1]-le[i+1])), sc[i+1]-sp[i+1]);
		sp[i+1]+=l;
		sp[i]-=l;
		le[i]=(op[i]-(up[i]+(sp[i+1]-le[i+1])));
	}
	//~ for (int i=0;i<n;i++){
		//~ cout<<sp[i]<<" ";
	//~ }
	//~ cout<<endl;

	int ans=0;
	for(int i=0;i<n-1;i++){
		ans+=up[i];
	}
	cout<<"YES\n";
	cout<<ans<<endl;
	vector<tuple<int,int,int>> out;
	for(int i=n-2;i>=0;i--){
		out.pb({op[i]-up[i]-sp[i+1], up[i],sp[i+1]});
		sp[i]-=op[i]-up[i]-sp[i+1];
		assert(sp[i] >= 0 && sp[i+1] >= 0 && up[i] >= 0);

	}
	reverse(out.begin(),out.end());
	for(auto it:out){
		cout<<g0(it)<<" "<<g1(it)<<" "<<g2(it)<<endl;
	}

	//~ for(int i=0;i<n-1;i++){
		//~ cout<<sp[i]<<" "<<up[i]<<" "<<op[i]-(up[i]+sp[i])<<endl;
		//~ sp[i+1]-=op[i]-(up[i]+sp[i]);
		//~ assert(sp[i] >= 0 && sp[i+1] >= 0 && up[i] >= 0);

	//~ }
}

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