#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int ll
const int INF = 1e18, MAXN = 210, MOD = 1e9 + 7;
int n, l;
int dp[MAXN][MAXN][MAXN][2];
int dist(int a, int b) {
return min(((a - b) % l + l) % l, ((b - a) % l + l) % l);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n >> l;
vector<pair<int, int>> left(n);
for (auto& i : left)
cin >> i.first;
for (auto& i : left)
cin >> i.second;
auto right = left;
left.push_back({0, 0});
right.push_back({l, 0});
sort(all(left));
sort(rall(right));
int res = 0;
for (int lb = 0; lb <= n; lb++)
for (int rb = 0; lb + rb <= n; rb++)
for (int cnt = 0; cnt <= n; cnt++)
dp[lb][rb][cnt][0] = dp[lb][rb][cnt][1] = INF;
for (int lb = 1; lb <= n; lb++) {
if (dist(0, left[lb].first) <= left[lb].second) {
dp[lb][0][1][0] = dist(0, left[lb].first);
res = 1;
}
}
for (int rb = 1; rb <= n; rb++) {
if (dist(0, right[rb].first) <= right[rb].second) {
dp[0][rb][1][1] = dist(0, right[rb].first);
res = 1;
}
}
for (int cnt = 2; cnt <= n; cnt++) {
for (int lb = 0; lb <= n; lb++) {
for (int rb = 0; lb + rb <= n; rb++) {
if (lb > 0)
dp[lb][rb][cnt][0] = min(dp[lb][rb][cnt][0], dp[lb - 1][rb][cnt][0] + dist(left[lb - 1].first, left[lb].first));
if (rb > 0)
dp[lb][rb][cnt][0] = min(dp[lb][rb][cnt][0], dp[lb][rb - 1][cnt][1] + dist(right[rb - 1].first, left[lb].first));
if (lb > 0 and dp[lb - 1][rb][cnt - 1][0] + dist(left[lb - 1].first, left[lb].first) <= left[lb].second)
dp[lb][rb][cnt][0] = min(dp[lb][rb][cnt][0], dp[lb - 1][rb][cnt - 1][0] + dist(left[lb - 1].first, left[lb].first));
if (lb > 0 and dp[lb - 1][rb][cnt - 1][1] + dist(right[rb].first, left[lb].first) <= left[lb].second)
dp[lb][rb][cnt][0] = min(dp[lb][rb][cnt][0], dp[lb - 1][rb][cnt - 1][1] + dist(right[rb].first, left[lb].first));
if (lb > 0)
dp[lb][rb][cnt][1] = min(dp[lb][rb][cnt][1], dp[lb - 1][rb][cnt][0] + dist(left[lb - 1].first, right[rb].first));
if (rb > 0)
dp[lb][rb][cnt][1] = min(dp[lb][rb][cnt][1], dp[lb][rb - 1][cnt][1] + dist(right[rb - 1].first, right[rb].first));
if (rb > 0 and dp[lb][rb - 1][cnt - 1][1] + dist(right[rb - 1].first, right[rb].first) <= right[rb].second)
dp[lb][rb][cnt][1] = min(dp[lb][rb][cnt][1], dp[lb][rb - 1][cnt - 1][1] + dist(right[rb - 1].first, right[rb].first));
if (rb > 0 and dp[lb][rb - 1][cnt - 1][0] + dist(left[lb].first, right[rb].first) <= right[rb].second)
dp[lb][rb][cnt][1] = min(dp[lb][rb][cnt][1], dp[lb][rb - 1][cnt - 1][0] + dist(left[lb].first, right[rb].first));
dp[lb][rb][cnt][0] = min(dp[lb][rb][cnt][0], dp[lb][rb][cnt][1] + dist(left[lb].first, right[rb].first));
dp[lb][rb][cnt][1] = min(dp[lb][rb][cnt][1], dp[lb][rb][cnt][0] + dist(left[lb].first, right[rb].first));
if (dp[lb][rb][cnt][0] != INF or dp[lb][rb][cnt][1] != INF)
res = max(res, cnt);
}
}
}
cout << res;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
17 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
17 |
Correct |
1 ms |
596 KB |
Output is correct |
18 |
Correct |
1 ms |
724 KB |
Output is correct |
19 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
17 |
Correct |
1 ms |
596 KB |
Output is correct |
18 |
Correct |
515 ms |
54648 KB |
Output is correct |
19 |
Correct |
247 ms |
33280 KB |
Output is correct |
20 |
Correct |
96 ms |
17904 KB |
Output is correct |
21 |
Correct |
225 ms |
31444 KB |
Output is correct |
22 |
Correct |
332 ms |
40672 KB |
Output is correct |
23 |
Correct |
76 ms |
15288 KB |
Output is correct |
24 |
Incorrect |
54 ms |
12036 KB |
Output isn't correct |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
17 |
Correct |
1 ms |
596 KB |
Output is correct |
18 |
Correct |
1 ms |
724 KB |
Output is correct |
19 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |