#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, l;
const int MXN = 205;
int pos[MXN], by[MXN];
int dp[MXN][MXN][2][MXN];
priority_queue<pair<int, pair<pair<int, int>, pair<int, int>>>, vector<pair<int, pair<pair<int, int>, pair<int, int>>>>, greater<pair<int, pair<pair<int, int>, pair<int, int>>>>> proc;
bool can(int l, int r) {
if (r + 1 == l) return true;
if (l == 1 && r == n) return true;
return false;
}
int prev(int x) {
if (x == 1) return n;
return x - 1;
}
int next(int x) {
if (x == n) return 1;
return x + 1;
}
signed main() {
cin >> n >> l;
for (int i=1; i<=n; i++) {
cin >> pos[i];
}
for (int i=1; i<=n; i++) {
cin >> by[i];
}
if (n == 1) {
if (min(pos[1], l - pos[1]) <= by[1]) cout << 1 << endl;
else cout << 0 << endl;
return 0;
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
for (int f=0; f<2; f++) {
for (int g=0; g<=n; g++) {
dp[i][j][f][g] = LLONG_MAX;
}
}
}
}
proc.push({pos[1], {{1, 1}, {0, pos[1] <= by[1]}}});
proc.push({l-pos[n], {{n, n}, {1, (l - pos[n]) <= by[n]}}});
int lr = 0;
while (!proc.empty()) {
auto x = proc.top(); proc.pop();
int mtime = x.first;
int lbound = x.second.first.first;
int rbound = x.second.first.second;
int curr = x.second.second.first;
int taken = x.second.second.second;
lr = max(lr, taken);
if (dp[lbound][rbound][curr][taken] < mtime) continue;
dp[lbound][rbound][curr][taken] = mtime;
int at = (curr == 0 ? pos[lbound] : pos[rbound]);
if (can(lbound, rbound)) continue;
int before = prev(lbound);
int dist = abs(at - pos[before]);
proc.push({min(dist, l - dist) + mtime, {{before, rbound}, {0, taken + ((min(dist, l - dist) + mtime) <= by[before])}}});
int after = next(rbound);
dist = abs(at - pos[after]);
proc.push({min(dist, l - dist) + mtime, {{lbound, after}, {1, taken + ((min(dist, l - dist) + mtime) <= by[after])}}});
}
cout << lr << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
640 KB |
Output is correct |
| 4 |
Correct |
1 ms |
512 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
896 KB |
Output is correct |
| 7 |
Correct |
1 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
640 KB |
Output is correct |
| 9 |
Correct |
1 ms |
896 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
256 KB |
Output is correct |
| 12 |
Correct |
1 ms |
896 KB |
Output is correct |
| 13 |
Correct |
1 ms |
896 KB |
Output is correct |
| 14 |
Correct |
1 ms |
512 KB |
Output is correct |
| 15 |
Correct |
1 ms |
512 KB |
Output is correct |
| 16 |
Correct |
1 ms |
896 KB |
Output is correct |
| 17 |
Correct |
1 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
640 KB |
Output is correct |
| 4 |
Correct |
1 ms |
512 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
896 KB |
Output is correct |
| 7 |
Correct |
1 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
640 KB |
Output is correct |
| 9 |
Correct |
1 ms |
896 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
256 KB |
Output is correct |
| 12 |
Correct |
1 ms |
896 KB |
Output is correct |
| 13 |
Correct |
1 ms |
896 KB |
Output is correct |
| 14 |
Correct |
1 ms |
512 KB |
Output is correct |
| 15 |
Correct |
1 ms |
512 KB |
Output is correct |
| 16 |
Correct |
1 ms |
896 KB |
Output is correct |
| 17 |
Correct |
1 ms |
896 KB |
Output is correct |
| 18 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 19 |
Correct |
1 ms |
640 KB |
Output is correct |
| 20 |
Correct |
1 ms |
896 KB |
Output is correct |
| 21 |
Correct |
1 ms |
1020 KB |
Output is correct |
| 22 |
Correct |
1 ms |
640 KB |
Output is correct |
| 23 |
Correct |
1 ms |
1152 KB |
Output is correct |
| 24 |
Correct |
1 ms |
896 KB |
Output is correct |
| 25 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 26 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 27 |
Correct |
1 ms |
512 KB |
Output is correct |
| 28 |
Correct |
1 ms |
640 KB |
Output is correct |
| 29 |
Correct |
1 ms |
1152 KB |
Output is correct |
| 30 |
Correct |
2 ms |
1152 KB |
Output is correct |
| 31 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 32 |
Correct |
1 ms |
896 KB |
Output is correct |
| 33 |
Correct |
1 ms |
1152 KB |
Output is correct |
| 34 |
Correct |
1 ms |
1152 KB |
Output is correct |
| 35 |
Correct |
2 ms |
1152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
640 KB |
Output is correct |
| 4 |
Correct |
1 ms |
512 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
896 KB |
Output is correct |
| 7 |
Correct |
1 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
640 KB |
Output is correct |
| 9 |
Correct |
1 ms |
896 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
256 KB |
Output is correct |
| 12 |
Correct |
1 ms |
896 KB |
Output is correct |
| 13 |
Correct |
1 ms |
896 KB |
Output is correct |
| 14 |
Correct |
1 ms |
512 KB |
Output is correct |
| 15 |
Correct |
1 ms |
512 KB |
Output is correct |
| 16 |
Correct |
1 ms |
896 KB |
Output is correct |
| 17 |
Correct |
1 ms |
896 KB |
Output is correct |
| 18 |
Execution timed out |
2092 ms |
145076 KB |
Time limit exceeded |
| 19 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
640 KB |
Output is correct |
| 4 |
Correct |
1 ms |
512 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
896 KB |
Output is correct |
| 7 |
Correct |
1 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
640 KB |
Output is correct |
| 9 |
Correct |
1 ms |
896 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
256 KB |
Output is correct |
| 12 |
Correct |
1 ms |
896 KB |
Output is correct |
| 13 |
Correct |
1 ms |
896 KB |
Output is correct |
| 14 |
Correct |
1 ms |
512 KB |
Output is correct |
| 15 |
Correct |
1 ms |
512 KB |
Output is correct |
| 16 |
Correct |
1 ms |
896 KB |
Output is correct |
| 17 |
Correct |
1 ms |
896 KB |
Output is correct |
| 18 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 19 |
Correct |
1 ms |
640 KB |
Output is correct |
| 20 |
Correct |
1 ms |
896 KB |
Output is correct |
| 21 |
Correct |
1 ms |
1020 KB |
Output is correct |
| 22 |
Correct |
1 ms |
640 KB |
Output is correct |
| 23 |
Correct |
1 ms |
1152 KB |
Output is correct |
| 24 |
Correct |
1 ms |
896 KB |
Output is correct |
| 25 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 26 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 27 |
Correct |
1 ms |
512 KB |
Output is correct |
| 28 |
Correct |
1 ms |
640 KB |
Output is correct |
| 29 |
Correct |
1 ms |
1152 KB |
Output is correct |
| 30 |
Correct |
2 ms |
1152 KB |
Output is correct |
| 31 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 32 |
Correct |
1 ms |
896 KB |
Output is correct |
| 33 |
Correct |
1 ms |
1152 KB |
Output is correct |
| 34 |
Correct |
1 ms |
1152 KB |
Output is correct |
| 35 |
Correct |
2 ms |
1152 KB |
Output is correct |
| 36 |
Execution timed out |
2092 ms |
145076 KB |
Time limit exceeded |
| 37 |
Halted |
0 ms |
0 KB |
- |
