Submission #711137

#	Time	Username	Problem	Language	Result	Execution time	Memory
711137		ld_minh4354	Rainy Markets (CCO22_day1problem2)	C++17	0 / 25	1618 ms	1048576 KiB

Main

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

#define int long long
#define fi first
#define se second
#define pb push_back
#define debug(x) cout<<#x<<": "<<x<<"\n"

int n,i,x,y,ans,xans[1000005],yans[1000005];
int b[1000005],p[1000005],u[1000005],dp[2005][205][405],dpmin[2005][405];

signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("input.000","r",stdin);
//	freopen("output.000","w",stdout);
//	srand((unsigned)time(NULL));
//	rand()
	
	cin>>n;
	for (i=1;i<n+1;i++) cin>>b[i];
	for (i=1;i<n;i++) cin>>p[i];
	for (i=1;i<n;i++) cin>>u[i];
	
	for (i=1;i<n+1;i++) for (x=0;x<=200;x++) for (y=0;y<=400;y++) dp[i][x][y]=1e18;
	for (i=1;i<n+1;i++) for (y=0;y<=400;y++) dpmin[i][y]=1e18;
	
	for (x=0;x<=u[1];x++) for (y=0;y<=b[2];y++)
	if (x+y<=p[1] and p[1]-x-y<=b[1]) dp[1][x][y]=x;
	
	for (y=0;y<=b[2];y++)
	{
		if (y>0) dpmin[1][y]=dpmin[1][y-1];
		for (x=0;x<=u[1];x++) dpmin[1][y]=min(dpmin[1][y], dp[1][x][y]);
	}
	
	for (i=2;i<n;i++)
	{
		for (x=0;x<=u[i];x++) for (y=0;y<=b[i+1];y++)
		if (x+y<=p[i] and p[i]-x-y<=b[i]) dp[i][x][y]=x+dpmin[i-1][b[i]-(p[i]-x-y)];
		
		for (y=0;y<=b[i+1];y++)
		{
			if (y>0) dpmin[i][y]=dpmin[i][y-1];
			for (x=0;x<=u[i];x++) dpmin[i][y]=min(dpmin[i][y], dp[i][x][y]);
		}
	}
	
	ans=1e18;
	for (y=0;y<=b[n];y++) ans=min(ans, dpmin[n-1][y]);
	
	if (ans>3e15) cout<<"NO";else
	{
		cout<<"YES\n"<<ans<<"\n";
		
		for (x=0;x<=u[n-1];x++) for (y=0;y<=b[n];y++)
		if (x+y<=p[n-1] and p[n-1]-x-y<=b[n-1])
		if (dp[n-1][x][y]==ans)
		{
			xans[n-1]=x;
			yans[n-1]=y;
		}
		
		for (i=n-2;i>0;i--) xans[i]=-1;
		
		for (i=n-2;i>0;i--)
		for (x=0;x<=u[i];x++)
		if (x+b[i+1]-(p[i+1]-xans[i+1]-yans[i+1])<=p[i] and p[i]-x-b[i+1]+(p[i+1]-xans[i+1]-yans[i+1])<=b[i])
		if (xans[i+1]+dp[i][x][b[i+1]-(p[i+1]-xans[i+1]-yans[i+1])]==dp[i+1][xans[i+1]][yans[i+1]])
		{
			xans[i]=x;
			yans[i]=b[i+1]-(p[i+1]-xans[i+1]-yans[i+1]);
		}
		
		for (i=1;i<n;i++) cout<<p[i]-xans[i]-yans[i]<<" "<<xans[i]<<" "<<yans[i]<<"\n";
	}
}

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