#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define pb push_back
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
const int mxn=405;
int dp[mxn][mxn][mxn/2][2];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
setio();
int n,l;
cin>>n>>l;
vector<int>pos;
vector<int>time;
pos.pb(0);
for(int i=0;i<n;i++){
int x;
cin>>x;
pos.pb(x);
}
for(int i=1;i<=n;i++){
pos.pb(pos[i]+l);
}
time.pb(0);
for(int i=0;i<n;i++){
int t;
cin>>t;
time.pb(t);
}
for(int i=1;i<=n;i++)time.pb(time[i]);
for(int i=0;i<=2*n;i++){
for(int j=0;j<=2*n;j++){
for(int k=0;k<=2*n;k++){
dp[i][j][k][0]=dp[i][j][k][1]=4e18;
}
}
}
for(int i=1;i<=2*n;i++){
if(abs(pos[i]-l)<=time[i])dp[i][i][1][0]=dp[i][i][1][1]=abs(pos[i]-l);
}
int ans=0;
for(int k=1;k<=n;k++){
for(int l=2*n;l>=1;l--){
for(int r=l+k-1;r<=2*n;r++){
dp[l][r][k][0]=min(dp[l+1][r][k][0]+abs(pos[l]-pos[l+1]),
dp[l+1][r][k][1]+abs(pos[l]-pos[r]));
if(dp[l+1][r][k-1][0]+abs(pos[l]-pos[l+1])<=time[l])dp[l][r][k][0]=min(dp[l][r][k][0],dp[l+1][r][k-1][0]+abs(pos[l]-pos[l+1]));
if(dp[l+1][r][k-1][1]+abs(pos[l]-pos[r])<=time[l])dp[l][r][k][0]=min(dp[l][r][k][0],dp[l+1][r][k-1][1]+abs(pos[l]-pos[r]));
dp[l][r][k][1]=min(dp[l][r-1][k][0]+abs(pos[r]-pos[l]),
dp[l][r-1][k][1]+abs(pos[r-1]-pos[r]));
if(dp[l][r-1][k-1][0]+abs(pos[l]-pos[r])<=time[r])dp[l][r][k][1]=min(dp[l][r][k][1],dp[l][r-1][k-1][0]+abs(pos[l]-pos[r]));
if(dp[l][r-1][k-1][1]+abs(pos[r-1]-pos[r])<=time[r])dp[l][r][k][1]=min(dp[l][r][k][1],dp[l][r-1][k-1][1]+abs(pos[r-1]-pos[r]));
if(r-l+1<=n and dp[l][r][k][0]<4e18 or dp[l][r][k][1]<4e18){
ans=max(ans,k);
}
//cout<<l<<' '<<r<<' '<<k<<' '<<dp[l][r][k][0]<<' '<<dp[l][r][k][1]<<'\n';
}
}
}
cout<<ans<<'\n';
}
/*
dp[l][r][k][0/1] min time to collect k stamps between lth~rth stamp 0->ends at l 1->ends at r
dp[l][r][k][0]=if(dp[l+1][r][k-1][0]+x[l]-x[l-1]<=t[l])dp[l-1][r][k-1][0]+x[l]-x[l-1]
if(dp[l+1][r][k-1][1]+x[l]-x[r]<=t[l])
dp[l-1][r][k][0]+x[l]-x[l-1]
dp[l-1][r][k][1]+x[l]-x[r]
*/
Compilation message
ho_t3.cpp: In function 'int main()':
ho_t3.cpp:65:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
65 | if(r-l+1<=n and dp[l][r][k][0]<4e18 or dp[l][r][k][1]<4e18){
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
