Submission #625424

#	Time	Username	Problem	Language	Result	Execution time	Memory
625424		Augustyn	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	162 ms	33088 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
int n,l,x[401],t[401],odp;
int dp[201][201][201][2];
int odl(int a,int b)
{
	return min(abs(x[a]-x[b]),min(abs(l-x[a]+x[b]),abs(l-x[b]+x[a])));
}
int main()
{
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;++i)
		scanf("%d",&x[i]);
	for(int i=1;i<=n;++i)
		scanf("%d",&t[i]);
	for(int i=0;i<=n;++i)
	{
		for(int j=0;j+i<=n;++j)
		{
			for(int k=0;k<=j+i;++k)
			{
				dp[i][j][k][0]=1500000000;
				dp[i][j][k][1]=1500000000;
				if(i)
				{
					dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k][0]+odl(i-1,i));
					dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k][1]+odl(n+1-j,i));
					if(k)
					{
						if(dp[i-1][j][k-1][0]+odl(i-1,i)<=t[i])
						dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k-1][0]+odl(i-1,i));
						if(dp[i-1][j][k-1][1]+odl(n+1-j,i)<=t[i])
						dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k-1][1]+odl(n+1-j,i));
					}
				}
				if(j)
				{
					dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j-1][k][0]+odl(i,n+1-j));
					dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j-1][k][1]+odl(n+1-j+1,n+1-j));
					if(k)
					{
						if(dp[i][j-1][k-1][0]+odl(i,n+1-j)<=t[n+1-j])
						dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j-1][k-1][0]+odl(i,n+1-j));
						if(dp[i][j-1][k-1][1]+odl(n+1-j+1,n+1-j)<=t[n+1-j])
						dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j-1][k-1][1]+odl(n+1-j+1,n+1-j));
					}
				}
				if(dp[i][j][k][0]<1500000000)
					odp=max(odp,k);
				if(dp[i][j][k][1]<1500000000)
					odp=max(odp,k);
				if(i==j&&j==k&&k==0)
				{
					dp[i][j][k][0]=0;
					dp[i][j][k][1]=0;
				}

			}
			dp[i][j][i+j+1][0]=1500000000;
			dp[i][j][i+j+1][1]=1500000000;
		}
	}
	printf("%d",odp);
	return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d%d",&n,&l);
      |  ~~~~~^~~~~~~~~~~~~~
ho_t3.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%d",&x[i]);
      |   ~~~~~^~~~~~~~~~~~
ho_t3.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d",&t[i]);
      |   ~~~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75