Submission #710936

#	Time	Username	Problem	Language	Result	Execution time	Memory
710936		penguin133	Rainy Markets (CCO22_day1problem2)	C++17	0 / 25	615 ms	468 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, A[1000005], B[1000005], C[1000005];
pii ans[1000005];
int dp[2005][4005], P[1000005];

void solve(){
	cin >> n;
	for(int i=1;i<=n;i++)cin >> A[i];
	for(int i=1;i<n;i++)cin >> B[i];
	for(int i=1;i<n;i++)cin >> C[i];
	for(int i=1;i<n;i++){
		/*
		P[A[i] + 1] = 1e18;
		for(int j=A[i];j>=0;j--){
			P[j] = min(P[j+1], dp[i-1][j] + max(0ll, B[i] - A[i+1] - j));
		}
		
		for(int j=0;j<=A[i+1];j++){
			if(B[i] - A[i+1] + j - C[i] > A[i])dp[i][j] = 1e18;
			else dp[i][j] = P[max(0ll, B[i] - A[i+1] + j - C[i])] + j;
		}
		*/
		for(int j=0;j<=A[i+1];j++){
			dp[i][j] = 1e18;
			for(int k=0;k<=A[i];k++){
				int ext = B[i] - (A[i+1] - j) - k;
				if(ext > C[i])continue;
				ext = max(ext, 0ll);
				dp[i][j] = min(dp[i][j], ext + dp[i-1][k]);
			}
		}
	}
	int mn = 1e18, idx = -1;
	for(int i=0;i<=A[n];i++)if(mn > dp[n-1][i])mn = dp[n-1][i], idx = i;
	if(mn >= (int)1e17){
		cout << "NO\n";
		return;
	}
	int x1 = n-1, x2 = idx;
	while(x1 >= 1){
		//cout << x1 << ' ' << x2 << '\n';
		int nd = -1, mn2=  1e18;
		for(int j=0;j<=A[x1];j++){
			int ext = (B[x1] - (A[x1 + 1] - x2) - j);
			if(ext > C[x1])continue;
			ext = max(ext, 0ll);
			if(dp[x1-1][j] + ext < mn2){
				mn2 = dp[x1-1][j] + ext;
				nd = j;
			}
		}
		ans[x1].se.se = A[x1+1] - x2;
		ans[x1].se.fi = B[x1] - (A[x1+1] - x2) - nd;
      	ans[x1].se.fi = max(ans[x1].se.fi, 0ll);
		ans[x1].fi = nd;
		x1--;
		x2 = nd;
	}
	cout << "YES\n";
	cout << mn << '\n';
	for(int i=1;i<n;i++)cout << ans[i].fi << ' ' << ans[i].se.fi << ' ' << ans[i].se.se << '\n';
	
	/*
	for(int i=1;i<n;i++){
		ans[i].fi = min(A[i], B[i]);
		B[i] -= min(B[i], A[i]);
		if(B[i] > A[i+1]){
			cout << "NO\n";
			return;
		}
		ans[i].se = B[i];
		A[i+1] -= B[i];
	}
	cout << "YES\n 0\n";
	for(int i=1;i<n;i++)cout << ans[i].fi << ' ' << 0 << ' ' << ans[i].se << '\n';
	*/
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

Main.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main(){
      | ^~~~

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