oj.uz

Submission #711143

# Submission time Handle Problem Language Result Execution time Memory
711143 2023-03-16T08:56:37 Z ld_minh4354 Rainy Markets (CCO22_day1problem2) C++17
0 / 25
 1500 ms 1048576 KB 
#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;
		}
		
		p[0]=b[0]=1e18;
		
		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-1] and p[i]-x-b[i+1]+(p[i+1]-xans[i+1]-yans[i+1])<=b[i-1])
		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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2260 KB Output is correct
2 Execution timed out 1618 ms 1037384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2260 KB Output is correct
2 Correct 3 ms 2888 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Runtime error 457 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2260 KB Output is correct
2 Correct 3 ms 2888 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Runtime error 457 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2260 KB Output is correct
2 Execution timed out 1618 ms 1037384 KB Time limit exceeded
3 Halted 0 ms 0 KB -