//#define NDEBUG
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define F first
#define S second
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
if(pvaspace) b << " "; pvaspace=true;\
b << pva;\
}\
b << "\n";}
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tiii tuple<int, int, int>
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) ((a) / (b) + !!((a) % (b)))
//#define TEST
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
using namespace __gnu_pbds;
const ll MOD = 1000000007;
const ll MAX = 2147483647;
template<typename A, typename B>
ostream &operator<<(ostream &o, pair<A, B> p){
return o << '(' << p.F << ',' << p.S << ')';
}
ll dis(int a, int b, int l){
return min(abs(a - b), l - abs(a - b));
}
int main(){
StarBurstStream
int n, L;
cin >> n >> L;
vector<int> x(n), t(n);
for(int i = 0; i < n; i++) cin >> x[i];
for(int i = 0; i < n; i++) cin >> t[i];
vector<vector<vector<ll>>> dpl(n, vector<vector<ll>>(n, vector<ll>(n + 1, 1 << 30))),
dpr(n, vector<vector<ll>>(n, vector<ll>(n + 1, 1 << 30)));
for(int len = 1; len <= n; len++){
for(int l = n - len; ; l = (l + 1) % n){
int r = (l + len - 1) % n;
if(len == 1){
dpl[l][r][0] = dis(x[l], 0, L);
dpr[l][r][0] = dis(x[l], 0, L);
if(dis(x[l], 0, L) <= t[l]){
dpl[l][r][1] = dis(x[l], 0, L);
dpr[l][r][1] = dis(x[l], 0, L);
}
if(l == 0) break;
continue;
}
int l1 = (l + 1) % n;
int r1 = (r - 1 + n) % n;
dpl[l][r][0] = min(dpl[l1][r][0] + dis(x[l], x[l1], L), dpr[l1][r][0] + dis(x[l], x[r], L));
dpr[l][r][0] = min(dpr[l][r1][0] + dis(x[r], x[r1], L), dpl[l][r1][0] + dis(x[l], x[r], L));
for(int c = 1; c <= n; c++){
dpl[l][r][c] = min(dpl[l][r][c], dpl[l1][r][c] + dis(x[l], x[l1], L));
dpl[l][r][c] = min(dpl[l][r][c], dpr[l1][r][c] + dis(x[l], x[r], L));
if(dpl[l1][r][c - 1] + dis(x[l], x[l1], L) <= t[l])
dpl[l][r][c] = min(dpl[l][r][c], dpl[l1][r][c - 1] + dis(x[l], x[l1], L));
if(dpr[l1][r][c - 1] + dis(x[l], x[r], L) <= t[l])
dpl[l][r][c] = min(dpl[l][r][c], dpr[l1][r][c - 1] + dis(x[l], x[r], L));
dpr[l][r][c] = min(dpr[l][r][c], dpr[l][r1][c] + dis(x[r], x[r1], L));
dpr[l][r][c] = min(dpr[l][r][c], dpl[l][r1][c] + dis(x[r], x[l], L));
if(dpr[l][r1][c - 1] + dis(x[r], x[r1], L) <= t[r])
dpr[l][r][c] = min(dpr[l][r][c], dpr[l][r1][c - 1] + dis(x[r], x[r1], L));
if(dpl[l][r1][c - 1] + dis(x[r], x[l], L) <= t[r])
dpr[l][r][c] = min(dpr[l][r][c], dpl[l][r1][c - 1] + dis(x[r], x[l], L));
}
if(l == 0) break;
}
}
int ans = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
for(int k = 0; k <= n; k++){
if(dpl[i][j][k] != (1 << 30) || dpr[i][j][k] != (1 << 30)){
// cerr << i << " " << j << " " << k << "\n";
ans = max(ans, k);
}
}
}
}
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
