Submission #224053

#	Time	Username	Problem	Language	Result	Execution time	Memory
224053		jamielim	Collecting Stamps 3 (JOI20_ho_t3)	C++14	0 / 100	5 ms	512 KiB

ho_t3

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

const long long INF=1012345678012345LL;

int main(){
	int n;long long l;
	scanf("%d%lld",&n,&l);
	long long x[n+2],t[n+2];
	x[0]=0;x[n+1]=l;t[0]=t[n+1]=INF;
	for(int i=1;i<=n;i++)scanf("%lld",&x[i]);
	for(int i=1;i<=n;i++)scanf("%lld",&t[i]);
	long long dp[n+2][n+2][n+1][2]; //time
	for(int i=0;i<n+2;i++){
		for(int j=0;j<n+2;j++){
			for(int k=0;k<=n;k++)dp[i][j][k][0]=dp[i][j][k][1]=INF;
		}
	}
	dp[0][n+1][0][0]=0;dp[0][n+1][0][1]=0;
	for(int k=0;k<=n;k++){
		for(int i=0;i<=n;i++){
			for(int j=n+1;j>=1;j--){
					if(i>0){
						if(k>0){
							if(dp[i-1][j][k-1][0]<INF&&dp[i-1][j][k-1][0]+x[i]-x[i-1]<=t[i])
								dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k-1][0]+x[i]-x[i-1]);
							if(dp[i-1][j][k-1][1]<INF&&dp[i-1][j][k-1][1]+l-(x[j]-x[i])<=t[i])
								dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k-1][1]+l-(x[j]-x[i]));
						}
							if(dp[i-1][j][k][0]<INF)dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k][0]+x[i]-x[i-1]);
							if(dp[i-1][j][k][1]<INF)dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k][1]+l-(x[j]-x[i]));
					}
					if(j<n+1){
						if(k>0){
							if(dp[i][j+1][k-1][0]<INF&&dp[i][j+1][k-1][0]+l-(x[j]-x[i])<=t[j])
								dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k-1][0]+l-(x[j]-x[i]));
							if(dp[i][j+1][k-1][1]<INF&&dp[i][j+1][k-1][1]+x[j+1]-x[j]<=t[j])
								dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k-1][1]+x[j+1]-x[j]);
						}
							if(dp[i][j+1][k][0]<INF)dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k][0]+l-(x[j]-x[i]));
							if(dp[i][j+1][k][1]<INF)dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k][1]+x[j+1]-x[j]);
					}
					//printf("%lld %lld ",dp[i][j][0],dp[i][j][1]);
					//dp[i][j][k][0]=min(dp[i][j][k][0],dp[i][j][k][1]+l-(x[j]-x[i]));
					//dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j][k][0]+l-(x[j]-x[i]));
					//printf("%lld %lld\n",dp[i][j][0],dp[i][j][1]);
			}
			//printf("\n");
		}
	}
	
	int ans=0;
	for(int i=0;i<n+2;i++){
		for(int j=0;j<n+2;j++){
			for(int k=0;k<=n;k++){
				if(dp[i][j][k][0]<INF||dp[i][j][k][1]<INF){
					ans=max(ans,k);
				}
			}
		}
	}
	//for(int i=0;i<n+2;i++){for(int j=0;j<n+2;j++)printf("%lld ",dp[i][j][0]);printf("\n");}
	//for(int i=0;i<n+2;i++){for(int j=0;j<n+2;j++)printf("%lld ",dp[i][j][1]);printf("\n");}
	printf("%d",ans);
}

Compilation message (stderr)

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

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