// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
// #include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
using namespace std;
#define int long long
#define y1 y11
#define double long double
#define less less228
#define left left228
#define right right228
#define list list228
template<typename T> void uin(T &a, T b) {
if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
if (b > a) a = b;
}
// random_device rnd;
// template<typename T> void shuffle(vector< T > &v) {
// for (int i = 1; i < (int)v.size(); ++i) {
// swap(v[rnd() % i], v[i]);
// }
// for (int i = (int)v.size() - 1; i; --i) {
// swap(v[rnd() % i], v[i]);
// }
// }
const int N = 202;
const int INF = 1e17 + 228;
int n, L;
int x[N], t[N];
int dp[N][N][N][2];
int dist(int x, int y) {
return min(abs(x - y), L - abs(x - y));
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> L;
for (int i = 1; i <= n; ++i) {
cin >> x[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 = 0; k <= n; ++k) {
dp[i][j][k][0] = dp[i][j][k][1] = INF;
}
}
}
for (int i = 1; i <= n; ++i) {
dp[i][i][0][0] = dp[i][i][0][1] = dist(0, x[i]);
if (dist(0, x[i]) <= t[i]) {
dp[i][i][1][0] = dp[i][i][1][1] = dist(0, x[i]);
}
}
for (int LEN = 0; LEN < n - 1; ++LEN) {
for (int l = 1; l <= n; ++l) {
int r = l + LEN;
if (r > n) r -= n;
// (l, r)
int bl = l - 1;
if (bl == 0) bl = n;
int ar = r + 1;
if (ar == n + 1) ar = 1;
for (int k = 0; k <= LEN + 1; ++k) {
uin(dp[bl][r][k][0], dp[l][r][k][0] + dist(x[l], x[bl]));
if (dp[l][r][k][0] + dist(x[l], x[bl]) <= t[bl]) {
uin(dp[bl][r][k + 1][0], dp[l][r][k][0] + dist(x[l], x[bl]));
}
uin(dp[l][ar][k][1], dp[l][r][k][0] + dist(x[l], x[ar]));
if (dp[l][r][k][0] + dist(x[l], x[ar]) <= t[ar]) {
uax(dp[l][ar][k + 1][1], dp[l][r][k][0] + dist(x[l], x[ar]));
}
uin(dp[l][ar][k][1], dp[l][r][k][1] + dist(x[r], x[ar]));
if (dp[l][r][k][1] + dist(x[r], x[ar]) <= t[ar]) {
uin(dp[l][ar][k + 1][1], dp[l][r][k][1] + dist(x[r], x[ar]));
}
uin(dp[bl][r][k][0], dp[l][r][k][1] + dist(x[r], x[bl]));
if (dp[l][r][k][1] + dist(x[r], x[bl]) <= t[bl]) {
uin(dp[bl][r][k + 1][0], dp[l][r][k][1] + dist(x[r], x[bl]));
}
}
}
}
int answer = 0;
for (int l = 1; l <= n; ++l) {
for (int r = 1; r <= n; ++r) {
for (int tet = 0; tet < 2; ++tet) {
for (int k = 1; k <= n; ++k) {
if (dp[l][r][k][tet] < INF / 2) {
uax(answer, k);
}
}
}
}
}
cout << answer << '\n';
return 0;
}
// RU_023
/*
6 25
3 4 7 17 21 23
11 7 17 10 8 10
---
4
5 20
4 5 8 13 17
18 23 15 7 10
---
5
4 19
3 7 12 14
2 0 5 4
---
0
10 87
9 23 33 38 42 44 45 62 67 78
15 91 7 27 31 53 12 91 89 46
---
5
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
632 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
504 KB |
Output is correct |
6 |
Correct |
5 ms |
760 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
632 KB |
Output is correct |
9 |
Correct |
5 ms |
760 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
760 KB |
Output is correct |
13 |
Correct |
5 ms |
760 KB |
Output is correct |
14 |
Correct |
5 ms |
504 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
6 ms |
760 KB |
Output is correct |
17 |
Correct |
5 ms |
760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
632 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
504 KB |
Output is correct |
6 |
Correct |
5 ms |
760 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
632 KB |
Output is correct |
9 |
Correct |
5 ms |
760 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
760 KB |
Output is correct |
13 |
Correct |
5 ms |
760 KB |
Output is correct |
14 |
Correct |
5 ms |
504 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
6 ms |
760 KB |
Output is correct |
17 |
Correct |
5 ms |
760 KB |
Output is correct |
18 |
Correct |
5 ms |
1016 KB |
Output is correct |
19 |
Correct |
5 ms |
636 KB |
Output is correct |
20 |
Correct |
5 ms |
760 KB |
Output is correct |
21 |
Correct |
5 ms |
1016 KB |
Output is correct |
22 |
Correct |
5 ms |
632 KB |
Output is correct |
23 |
Correct |
5 ms |
1016 KB |
Output is correct |
24 |
Correct |
5 ms |
888 KB |
Output is correct |
25 |
Incorrect |
5 ms |
1016 KB |
Output isn't correct |
26 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
632 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
504 KB |
Output is correct |
6 |
Correct |
5 ms |
760 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
632 KB |
Output is correct |
9 |
Correct |
5 ms |
760 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
760 KB |
Output is correct |
13 |
Correct |
5 ms |
760 KB |
Output is correct |
14 |
Correct |
5 ms |
504 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
6 ms |
760 KB |
Output is correct |
17 |
Correct |
5 ms |
760 KB |
Output is correct |
18 |
Correct |
108 ms |
102392 KB |
Output is correct |
19 |
Correct |
64 ms |
61944 KB |
Output is correct |
20 |
Correct |
36 ms |
32888 KB |
Output is correct |
21 |
Correct |
64 ms |
58360 KB |
Output is correct |
22 |
Correct |
75 ms |
75896 KB |
Output is correct |
23 |
Incorrect |
28 ms |
27896 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
632 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
504 KB |
Output is correct |
6 |
Correct |
5 ms |
760 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
632 KB |
Output is correct |
9 |
Correct |
5 ms |
760 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
760 KB |
Output is correct |
13 |
Correct |
5 ms |
760 KB |
Output is correct |
14 |
Correct |
5 ms |
504 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
6 ms |
760 KB |
Output is correct |
17 |
Correct |
5 ms |
760 KB |
Output is correct |
18 |
Correct |
5 ms |
1016 KB |
Output is correct |
19 |
Correct |
5 ms |
636 KB |
Output is correct |
20 |
Correct |
5 ms |
760 KB |
Output is correct |
21 |
Correct |
5 ms |
1016 KB |
Output is correct |
22 |
Correct |
5 ms |
632 KB |
Output is correct |
23 |
Correct |
5 ms |
1016 KB |
Output is correct |
24 |
Correct |
5 ms |
888 KB |
Output is correct |
25 |
Incorrect |
5 ms |
1016 KB |
Output isn't correct |
26 |
Halted |
0 ms |
0 KB |
- |