#include <bits/stdc++.h>
using namespace std;
#define f first
#define se second
template <typename T> void Min(T &a, T b) {
a = min(a, b);
}
template <typename T> void Max(T &a, T b) {
a = max(a, b);
}
const int inf = 0x3f3f3f3f;
const int N = 2e2 + 15;
int n, x, dp[2][N][N][N], ans;
pair <int, int> a[N];
// dp[last][l][r][items_taken] = min_time
inline int get(int c, int d) {
return min({abs(a[c].f - a[d].f), abs(a[c].f + x - a[d].f), abs(a[d].f + x - a[c].f)});
}
inline void calc(int l, int r, int len) {
// FROM L
int nxt = (l - 1 + n) % n;
int d = get(l, nxt);
if(nxt != r) {
for(int k = 0; k <= len; ++k) {
if(dp[0][l][r][k] + d <= a[nxt].se)
Min(dp[0][nxt][r][k+1], dp[0][l][r][k] + d);
else
Min(dp[0][nxt][r][k], dp[0][l][r][k] + d);
}
}
nxt = (r + 1 + n) % n;
if(nxt != l) {
d = get(l, nxt);
for(int k = 0; k <= len; ++k) {
if(dp[0][l][r][k] + d <= a[nxt].se)
Min(dp[1][l][nxt][k+1], dp[0][l][r][k] + d);
else
Min(dp[1][l][nxt][k], dp[0][l][r][k] + d);
}
}
// FROM R
nxt = (l - 1 + n) % n;
if(nxt != r) {
d = get(r, nxt);
for(int k = 0; k <= len; ++k) {
if(dp[1][l][r][k] + d <= a[nxt].se)
Min(dp[0][nxt][r][k+1], dp[1][l][r][k] + d);
else
Min(dp[0][nxt][r][k], dp[1][l][r][k] + d);
}
}
nxt = (r + 1 + n) % n;
if(nxt != l) {
d = get(r, nxt);
for(int k = 0; k <= len; ++k) {
if(dp[1][l][r][k] + d <= a[nxt].se)
Min(dp[1][l][nxt][k+1], dp[1][l][r][k] + d);
else
Min(dp[1][l][nxt][k], dp[1][l][r][k] + d);
}
}
}
main() {
memset(dp, 0x3f, sizeof(dp));
freopen("input.txt", "r", stdin);
cin >> n >> x;
for(int i = 1; i <= n; ++i)
cin >> a[i].f;
for(int i = 1; i <= n; ++i)
cin >> a[i].se;
reverse(a + 1, a + 1 + n);
++n;
dp[0][0][0][0] = 0;
for(int len = 0; len < n; ++len) {
for(int l = 0; l < n; ++l) {
int r = (l + len - 1) % n;
calc(l, r, len);
}
}
for(int k = n; k >= 0; --k)
for(int i = 0; i < 2; ++i)
for(int l = 0; l < n; ++l)
for(int r = 0; r < n; ++r)
if(dp[i][l][r][k] != inf) {
cout << k << endl;
return 0;
}
return 0;
}
Compilation message
ho_t3.cpp:72:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
ho_t3.cpp: In function 'int main()':
ho_t3.cpp:74:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("input.txt", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
78072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
78072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
78072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
78072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
