#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
int n,l;
cin>>n>>l;
int x[n+5],t[n+5];
for(int i=1; i<=n; i++) cin>>x[i];
for(int i=1; i<=n; i++) cin>>t[i];
x[n+1] = l;
int dp[n+5][n+5][n+5][2];
for(int i=0; i<n+5; i++){
for(int j=0; j<n+5; j++){
for(int k=0; k<n+5; k++){
dp[i][j][k][0]=1e17; dp[i][j][k][1]=1e17;
}
}
} //fill
dp[0][n+1][0][0] = 0;
dp[0][n+1][0][1] = 0;
int at0[n+5];
fill(at0,at0+n+5,1e17);
at0[0] = 0;
for(int k=0; k<=n; k++){
for(int j=n; j>0; j--){
dp[0][j][k][1] = min(dp[0][j+1][k][1] + (x[j+1]-x[j]), dp[0][j][k][1]);
if(k!=0){
if(dp[0][j+1][k-1][1] + (x[j+1]-x[j]) <= t[j]){
dp[0][j][k][1] = min(dp[0][j+1][k-1][1] + (x[j+1]-x[j]), dp[0][j][k][1]);
}
if(at0[k-1] + l-x[j] <= t[j]){
dp[0][j][k][1] = min(dp[0][j][k][1], at0[k-1] + l-x[j]);
}
}
}
for(int i=1; i<=n; i++){
dp[i][n+1][k][0] = min(dp[i-1][n+1][k][0] + (x[i]-x[i-1]), dp[i][n+1][k][0]);
if(k!=0){
if(dp[i-1][n+1][k-1][0] + (x[i]-x[i-1]) <= t[i]){
dp[i][n+1][k][0] = min(dp[i-1][n+1][k-1][0] + (x[i]-x[i-1]), dp[i][n+1][k][0]);
}
if(at0[k-1] + x[i] <= t[i]){
dp[i][n+1][k][0] = min(dp[i][n+1][k][0], at0[k-1] + x[i]);
}
}
for(int j=n; j>i; j--){
dp[i][j][k][1] = min(dp[i][j+1][k][1] + (x[j+1]-x[j]), dp[i][j][k][1]);
dp[i][j][k][0] = min(dp[i-1][j][k][0] + (x[i]-x[i-1]), dp[i][j][k][0]);
if(k!=0){
if(dp[i][j+1][k-1][1] + (x[j+1]-x[j]) <= t[j]){
dp[i][j][k][1] = min(dp[i][j+1][k-1][1] + (x[j+1]-x[j]), dp[i][j][k][1]);
}
if(dp[i-1][j][k-1][0] + (x[i]-x[i-1]) <= t[i]){
dp[i][j][k][0] = min(dp[i-1][j][k-1][0] + (x[i]-x[i-1]), dp[i][j][k][0]);
}
if(at0[k-1] + l-x[j] <= t[j]){
dp[i][j][k][1] = min(dp[i][j][k][1], at0[k-1] + l-x[j]);
}
if(at0[k-1] + x[i] <= t[i]){
dp[i][j][k][0] = min(dp[i][j][k][0], at0[k-1] + x[i]);
}
}
dp[i][j][k][0] = min(dp[i][j][k][0], at0[k]+x[i]);
dp[i][j][k][1] = min(dp[i][j][k][1], at0[k]+l-x[j]);
at0[k] = min(at0[k], dp[i][j][k][1] + l-x[j]);
at0[k] = min(at0[k], dp[i][j][k][0] + x[i]);
}
}
//cout<<at0[k]<<endl;
}
int an=0;
for(int i=0; i<=n; i++){
for(int j=0; j<=n; j++){
for(int k=1; k<=n; k++){
if(dp[i][j][k][0]<1e15 || dp[i][j][k][1]<1e15) an=max(an,k);
}
}
}
cout<<an;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
