#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 i=0;i<=n;i++){
for(int j=n+1;j>=1;j--){
for(int k=1;k<=n;k++){
if(i>0){
if(k>0){
if(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]);
//printf("a %lld ",dp[i-1][j][0]+x[i]-x[i-1]);
if(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]));
//printf("b %lld ",dp[i-1][j][1]+l-(x[j]-x[i]));
}
dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k][0]+x[i]-x[i-1]);
//printf("a %lld ",dp[i-1][j][0]+x[i]-x[i-1]);
dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k][1]+l-(x[j]-x[i]));
//printf("b %lld ",dp[i-1][j][1]+l-(x[j]-x[i]));
}
if(j<n+1){
if(k>0){
if(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]));
//printf("c %lld ",dp[i][j+1][0]+l-(x[j]-x[i]));
if(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]);
//printf("d %lld ",dp[i][j+1][1]+x[j+1]-x[j]);
}
dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k][0]+l-(x[j]-x[i]));
//printf("c %lld ",dp[i][j+1][0]+l-(x[j]-x[i]));
dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k][1]+x[j+1]-x[j]);
//printf("d %lld ",dp[i][j+1][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]);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
