Submission #710952

#	Time	Username	Problem	Language	Result	Execution time	Memory
710952		emptypringlescan	Rainy Markets (CCO22_day1problem2)	C++17	0 / 25	505 ms	61132 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	long long cap[n],pop[n-1],um[n-1];
	for(int i=0; i<n; i++) cin >> cap[i];
	for(int i=0; i<n-1; i++) cin >> pop[i];
	for(int i=0; i<n-1; i++) cin >> um[i];
	bool cant=false;
	long long left=cap[0];
	for(int i=0; i<n-1; i++){
		long long peep=pop[i]-left-um[i];
		left=cap[i+1]-peep;
		if(left<0) cant=true;
	}
	if(cant){
		cout << "NO";
		return 0;
	}
	long long fill[n],buy[n-1];
	memset(fill,0,sizeof(fill));
	memset(buy,0,sizeof(buy));
	for(int i=0; i<n-1; i++){
		long long space=cap[i]-fill[i],peep=pop[i];
		if(space>=pop[i]){
			fill[i]+=pop[i];
			continue;
		}
		fill[i]=cap[i];
		peep-=space;
		if(peep<=cap[i+1]){
			fill[i+1]=peep;
			continue;
		}
		fill[i+1]=cap[i+1];
		peep-=cap[i+1];
		buy[i]=peep;
	}
	long long sludge=0;
	for(int i=n-1; i>=0; i--){
		if(buy[i]>um[i]){
			sludge+=buy[i]-um[i];
			buy[i]=um[i];
		}
		if(buy[i]<um[i]){
			if(um[i]-buy[i]>=sludge){
				buy[i]+=sludge;
				sludge=0;
			}
			else{
				sludge-=um[i]-buy[i];
				buy[i]=um[i];
			}
		}
		//assert(sludge<=cap[i]);
		sludge-=cap[i]-fill[i];
		sludge=max(sludge,0LL);
	}/*
	for(int i=0; i<n; i++) cout << fill[i] << ' ';
	cout << '\n';
	for(int i=0; i<n-1; i++) cout << buy[i] << ' ';
	cout << '\n';*/
	assert(sludge==0);
	cout << "YES\n";
	long long cost=0,space=cap[0];
	for(int i=0; i<n-1; i++) cost+=buy[i];
	cout << cost << '\n';
	for(int i=0; i<n-1; i++){
		if(space<=pop[i]) cout << space << ' ';
		else cout << pop[i] << ' ';
		cout << buy[i] << ' ';
		if(pop[i]-space-buy[i]>0){
			cout << pop[i]-space-buy[i] << '\n';
			space=cap[i+1]-(pop[i]-space-buy[i]);
		}
		else{
			cout << 0 << '\n';
			space=cap[i+1];
		}
	}
}

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