#include <bits/stdc++.h>
#define int long long
using namespace std;
using pii = pair<int, int>;
int n, l;
vector<int> x, t;
int dis(int a, int b)
{
assert(0 <= a && 0 <= b && a <= n && b <= n);
return min(min(abs(x[a] - x[b]), x[a] + l - x[b]), l - x[a] + x[b]);
}
void solve()
{
cin >> n >> l;
x.assign(n + 1, 0), t.assign(n + 1, -1);
for (int i = 1; i <= n; ++i)
cin >> x[i];
for (int i = 1; i <= n; ++i)
cin >> t[i];
vector<vector<vector<vector<int>>>> dp(n + 1, vector<vector<vector<int>>>(n + 1, vector<vector<int>>(n + 1, vector<int>(2, LONG_LONG_MAX))));
// priority_queue<array<int, 5>> pq;
// array<int, 5> tmp;
dp[0][0][0][0] = dp[0][0][0][1] = 0;
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
if (i > j || i == 0)
{
dp[0][i][j][0] = dis(0, j) + dis(j, i);
dp[0][i][j][1] = dis(0, i) + dis(i, j);
}
// pq.emplace(tmp = {0, 0, 0, 0, 0});
// pq.emplace(tmp = {0, 0, 0, 0, 1});
/*
while (!pq.empty())
{
tmp = pq.top();
pq.pop();
int i = tmp[1], j = tmp[2], k = tmp[3], ll = tmp[4], d = -tmp[0];
if (d != dp[i][j][k][ll])
continue;
// cout << d << ' ';
if (ll == 0)
{
if ((j + n) % (n + 1) != k)
{
if (dp[i][(j + n) % (n + 1)][k][0] > dp[i][j][k][0] + dis(j, (j + n) % (n + 1)))
{
dp[i][(j + n) % (n + 1)][k][0] = dp[i][j][k][0] + dis(j, (j + n) % (n + 1));
pq.emplace(tmp = {-dp[i][(j + n) % (n + 1)][k][0], i, (j + n) % (n + 1), k, 0});
}
if (dp[i][j][k][0] + dis(j, (j + n) % (n + 1)) <= t[(j + n) % (n + 1)])
{
if (dp[i + 1][(j + n) % (n + 1)][k][0] > dp[i][j][k][0] + dis(j, (j + n) % (n + 1)))
{
dp[i + 1][(j + n) % (n + 1)][k][0] = dp[i][j][k][0] + dis(j, (j + n) % (n + 1));
pq.emplace(tmp = {-dp[i + 1][(j + n) % (n + 1)][k][0], i + 1, (j + n) % (n + 1), k, 0});
}
}
}
if (j != (k + 1) % (n + 1))
{
if (dp[i][j][(k + 1) % (n + 1)][1] > dp[i][j][k][0] + dis(j, (k + 1) % (n + 1)))
{
dp[i][j][(k + 1) % (n + 1)][1] = dp[i][j][k][0] + dis(j, (k + 1) % (n + 1));
pq.emplace(tmp = {-dp[i][j][(k + 1) % (n + 1)][1], i, j, (k + 1) % (n + 1), 1});
}
if (dp[i][j][k][0] + dis(j, (k + 1) % (n + 1)) <= t[(k + 1) % (n + 1)])
{
if (dp[i + 1][j][(k + 1) % (n + 1)][1] > dp[i][j][k][0] + dis(j, (k + 1) % (n + 1)))
{
dp[i + 1][j][(k + 1) % (n + 1)][1] = dp[i][j][k][0] + dis(j, (k + 1) % (n + 1));
pq.emplace(tmp = {-dp[i + 1][j][(k + 1) % (n + 1)][1], i + 1, j, (k + 1) % (n + 1), 1});
}
}
}
}
else
{
if ((j + n) % (n + 1) != k)
{
if (dp[i][(j + n) % (n + 1)][k][0] > dp[i][j][k][1] + dis(k, (j + n) % (n + 1)))
{
dp[i][(j + n) % (n + 1)][k][0] = dp[i][j][k][1] + dis(k, (j + n) % (n + 1));
pq.emplace(tmp = {-dp[i][(j + n) % (n + 1)][k][0], i, (j + n) % (n + 1), k, 0});
}
if (dp[i][j][k][1] + dis(k, (j + n) % (n + 1)) <= t[(j + n) % (n + 1)])
{
if (dp[i + 1][(j + n) % (n + 1)][k][0] > dp[i][j][k][1] + dis(k, (j + n) % (n + 1)))
{
dp[i + 1][(j + n) % (n + 1)][k][0] = dp[i][j][k][1] + dis(k, (j + n) % (n + 1));
pq.emplace(tmp = {-dp[i + 1][(j + n) % (n + 1)][k][0], i + 1, (j + n) % (n + 1), k, 0});
}
}
}
if (j != (k + 1) % (n + 1))
{
if (dp[i][j][(k + 1) % (n + 1)][1] > dp[i][j][k][1] + dis(k, (k + 1) % (n + 1)))
{
dp[i][j][(k + 1) % (n + 1)][1] = dp[i][j][k][1] + dis(k, (k + 1) % (n + 1));
pq.emplace(tmp = {-dp[i][j][(k + 1) % (n + 1)][1], i, j, (k + 1) % (n + 1), 1});
}
if (dp[i][j][k][1] + dis(k, (k + 1) % (n + 1)) <= t[(k + 1) % (n + 1)])
{
if (dp[i + 1][j][(k + 1) % (n + 1)][1] > dp[i][j][k][1] + dis(k, (k + 1) % (n + 1)))
{
dp[i + 1][j][(k + 1) % (n + 1)][1] = dp[i][j][k][1] + dis(k, (k + 1) % (n + 1));
pq.emplace(tmp = {-dp[i + 1][j][(k + 1) % (n + 1)][1], i + 1, j, (k + 1) % (n + 1), 1});
}
}
}
}
}
*/
// for (int a = 0; a < 100; ++a)
for (int i = 0; i < n; ++i)
for (int j = 0; j <= n; ++j)
for (int k = 0; k <= n; ++k)
{
if (dp[i][j][k][0] != LONG_LONG_MAX)
{
if ((j + n) % (n + 1) != k)
{
dp[i][(j + n) % (n + 1)][k][0] = min(dp[i][(j + n) % (n + 1)][k][0], dp[i][j][k][0] + dis(j, (j + n) % (n + 1)));
if (dp[i][j][k][0] + dis(j, (j + n) % (n + 1)) <= t[(j + n) % (n + 1)])
dp[i + 1][(j + n) % (n + 1)][k][0] = min(dp[i + 1][(j + n) % (n + 1)][k][0], dp[i][j][k][0] + dis(j, (j + n) % (n + 1)));
}
if (j != (k + 1) % (n + 1))
{
dp[i][j][(k + 1) % (n + 1)][1] = min(dp[i][j][(k + 1) % (n + 1)][1], dp[i][j][k][0] + dis(j, (k + 1) % (n + 1)));
if (dp[i][j][k][0] + dis(j, (k + 1) % (n + 1)) <= t[(k + 1) % (n + 1)])
dp[i + 1][j][(k + 1) % (n + 1)][1] = min(dp[i + 1][j][(k + 1) % (n + 1)][1], dp[i][j][k][0] + dis(j, (k + 1) % (n + 1)));
}
}
if (dp[i][j][k][1] != LONG_LONG_MAX)
{
if ((j + n) % (n + 1) != k)
{
dp[i][(j + n) % (n + 1)][k][0] = min(dp[i][(j + n) % (n + 1)][k][0], dp[i][j][k][1] + dis(k, (j + n) % (n + 1)));
if (dp[i][j][k][1] + dis(k, (j + n) % (n + 1)) <= t[(j + n) % (n + 1)])
dp[i + 1][(j + n) % (n + 1)][k][0] = min(dp[i + 1][(j + n) % (n + 1)][k][0], dp[i][j][k][1] + dis(k, (j + n) % (n + 1)));
}
if (j != (k + 1) % (n + 1))
{
dp[i][j][(k + 1) % (n + 1)][1] = min(dp[i][j][(k + 1) % (n + 1)][1], dp[i][j][k][1] + dis(k, (k + 1) % (n + 1)));
if (dp[i][j][k][1] + dis(k, (k + 1) % (n + 1)) <= t[(k + 1) % (n + 1)])
dp[i + 1][j][(k + 1) % (n + 1)][1] = min(dp[i + 1][j][(k + 1) % (n + 1)][1], dp[i][j][k][1] + dis(k, (k + 1) % (n + 1)));
}
}
}
int ans = 0;
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
for (int k = 0; k <= n; ++k)
for (int l = 0; l < 2; ++l)
if (dp[i][j][k][l] != LONG_LONG_MAX)
ans = max(ans, i);
cout << ans << '\n';
}
/*
6 25
3 4 7 17 21 23
11 7 17 10 8 10
5 20
4 5 8 13 17
18 23 15 7 10
4 19
3 7 12 14
2 0 5 4
10 87
9 23 33 38 42 44 45 62 67 78
15 91 7 27 31 53 12 91 89 46
*/
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
