#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=205;
ll n, d, a[nx], t[nx], dp[nx][nx][nx][2], res;
ll dist(ll a, ll b)
{
if (a>b) swap(a, b);
return min(b-a, a+d-b);
}
ll nxt(ll x)
{
if (x+1>n) return x+1-n;
return x+1;
}
ll prv(ll x)
{
if (x-1>0) return x-1;
return x-1+n;
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>d;
for (int i=1; i<=n; i++) cin>>a[i];
for (int i=1; i<=n; i++) cin>>t[i];
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) for (int k=1; k<=n; k++) dp[i][j][k][0]=dp[i][j][k][1]=1e18;
for (int i=1; i<=n; i++) dp[i][i][0][0]=dp[i][i][0][1]=dist(0, a[i]);
for (int i=1; i<=n; i++) if (dist(0, a[i])<=t[i]) dp[i][i][1][0]=dp[i][i][1][1]=dist(0, a[i]);
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
ll l=j, r=j+i;
if (r>n) r-=n;
dp[l][r][0][0]=dist(0, a[l]);
dp[l][r][0][1]=dist(0, a[r]);
for (int k=1; k<=i+1; k++)
{
dp[l][r][k][0]=min({dp[l][r][k][0], dp[nxt(l)][r][k][0]+dist(a[l], a[nxt(l)]), dp[nxt(l)][r][k][1]+dist(a[l], a[r])});
if (dp[nxt(l)][r][k-1][0]+dist(a[nxt(l)], a[l])<=t[l]) dp[l][r][k][0]=min(dp[l][r][k][0], dp[nxt(l)][r][k-1][0]+dist(a[nxt(l)], a[l]));
if (dp[nxt(l)][r][k-1][1]+dist(a[l], a[r])<=t[l]) dp[l][r][k][0]=min(dp[l][r][k][0], dp[nxt(l)][r][k-1][1]+dist(a[l], a[r]));
dp[l][r][k][1]=min({dp[l][r][k][1], dp[l][prv(r)][k][0]+dist(a[l], a[r]), dp[l][prv(r)][k][1]+dist(a[prv(r)], a[r])});
if (dp[l][prv(r)][k-1][0]+dist(a[l], a[r])<=t[r]) dp[l][r][k][1]=min(dp[l][r][k][1], dp[l][prv(r)][k-1][0]+dist(a[l], a[r]));
if (dp[l][prv(r)][k-1][1]+dist(a[prv(r)], a[r])<=t[r]) dp[l][r][k][1]=min(dp[l][r][k][1], dp[l][prv(r)][k-1][1]+dist(a[prv(r)], a[r]));
//cout<<"debug "<<l<<' '<<r<<' '<<k<<' '<<dp[l][r][k][0]<<' '<<dp[l][r][k][1]<<'\n';
}
}
}
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) for (int k=1; k<=n; k++) for (int t=0; t<2; t++) if (dp[i][j][k][t]<1e18) res=max(res, (ll)k);
cout<<res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
