#include<bits/stdc++.h>
using namespace std;
const long long maxn=502,inf=1e15+10;
pair<long long,long long>dp[maxn][maxn][maxn];
long long n,allx[maxn],allt[maxn],L;
long long fas(long long a,long long b){
long long ret=a-b;
ret+=L;
ret%=L;
//cout<<a<<" "<<b<<" "<<ret<<" wtf"<<endl;
return ret;
}
void upddp(long long l,long long r){
//cout<<l<<" "<<r<<" "<<dp[l][r][0].first<<" "<<dp[l][r][0].second<<"\n";
long long ll=(l-1)+n,rr=r+1;
ll%=n;
rr%=n;
for(long long i=0;i<maxn;i++){
if(dp[l][r][i].first!=inf){
//cout<<l<<" "<<r<<" "<<i<<" "<<dp[l][r][i].first<<" "<<dp[l][r][i].second<<'\n';
dp[ll][r][i].first=min(dp[ll][r][i].first,dp[l][r][i].first+fas(allx[l],allx[ll]));
dp[ll][r][i].second=min(dp[ll][r][i].second,dp[ll][r][i].first+fas(allx[r],allx[ll]));
if(fas(allx[l],allx[ll])+dp[l][r][i].first<=allt[ll]){
dp[ll][r][i+1].first=min(dp[ll][r][i+1].first,dp[l][r][i].first+fas(allx[l],allx[ll]));
dp[ll][r][i+1].second=min(dp[ll][r][i+1].second,dp[ll][r][i].first+fas(allx[r],allx[ll]));
}
dp[l][rr][i].second=min(dp[l][rr][i].second,dp[l][r][i].second+fas(allx[rr],allx[r]));
dp[l][rr][i].first=min(dp[l][rr][i].first,dp[l][rr][i].second+fas(allx[rr],allx[l]));
if(fas(allx[rr],allx[r])+dp[l][r][i].second<=allt[rr]){
dp[l][rr][i+1].second=min(dp[l][rr][i].second,dp[l][r][i].second+fas(allx[rr],allx[r]));
dp[l][rr][i+1].first=min(dp[l][rr][i+1].first,dp[l][rr][i+1].second+fas(allx[rr],allx[l]));
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(long long i=0;i<maxn;i++){
for(long long j=0;j<maxn;j++){
for(long long h=0;h<maxn;h++){
dp[i][j][h]=make_pair(inf,inf);
}
}
}
cin>>n>>L;
for(long long i=0;i<n;i++){
cin>>allx[i];
}
for(long long i=0;i<n;i++){
cin>>allt[i];
}
if(allx[0]<=allt[0]){
dp[0][0][0]=dp[0][0][1]=make_pair(allx[0],allx[0]);
}
else{
dp[0][0][0]=make_pair(allx[0],allx[0]);
}
if(fas(0,allx[n-1])<=allt[n-1]){
dp[n-1][n-1][0]=dp[n-1][n-1][1]=make_pair(fas(0,allx[n-1]),fas(0,allx[n-1]));
}
else{
dp[n-1][n-1][0]=make_pair(fas(0,allx[n-1]),fas(0,allx[n-1]));
}
for(long long i=0;i<n-1;i++){
upddp(0,0+i);
for(long long l=n-1;l>=n-i-1;l--){
upddp(l,(l+i)%n);
}
}
long long res=0;
for(long long i=0;i<n;i++){
int j=i-1+n;
j%=n;
for(long long h=0;h<=n;h++){
if(dp[i][j][h].first!=inf){
res=max(res,h);
}
}
}
cout<<res<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
335 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
335 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
335 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
335 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
