oj.uz

Submission #224053

# Submission time Handle Problem Language Result Execution time Memory
224053 2020-04-17T06:32:34 Z jamielim Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 5 ms 512 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 256 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 4 ms 256 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Incorrect 5 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 256 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 4 ms 256 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Incorrect 5 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 256 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 4 ms 256 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Incorrect 5 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 256 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 4 ms 256 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Incorrect 5 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -