This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 4;
const int N = 205;
int n, L, x[N], t[N], dp[N][N][N][2], INF;
void MIN(int &a, int b) {
if (a > b) a = b;
}
int dist(int from, int to) {
if (from > to) swap(from, to);
return min(x[to] - x[from], L - (x[to] - x[from]));
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen(".INP", "r", stdin);
//freopen(".OUT", "w", stdout);
cin >> n >> L;
for (int i = 1; i <= n; i++)
cin >> x[i];
for (int i = 1; i <= n; i++)
cin >> t[i];
memset(dp, 63, sizeof dp);
INF = dp[0][0][0][0];
dp[0][n + 1][0][0] = 0;
x[n + 1] = L;
for (int sz = n + 1; sz > 1; sz--) {
for (int i = 0; i <= n + 1 - sz; i++) {
int j = i + sz;
for (int k = 0; k <= n; k++) {
int x;
if (dp[i][j][k][0] != INF) {
x = dp[i][j][k][0] + dist(i, i + 1);
MIN(dp[i + 1][j][k + (x <= t[i + 1])][0], x);
x = dp[i][j][k][0] + dist(i, j - 1);
MIN(dp[i][j - 1][k + (x <= t[j - 1])][1], x);
}
if (dp[i][j][k][1] != INF) {
x = dp[i][j][k][1] + dist(j, i + 1);
MIN(dp[i + 1][j][k + (x <= t[i + 1])][0], x);
x = dp[i][j][k][1] + dist(j, j - 1);
MIN(dp[i][j - 1][k + (x <= t[j - 1])][1], x);
}
}
}
}
int ans = 0;
for (int k = 0; k <= n; k++)
for (int i = 0; i <= n; i++)
if (dp[i][i + 1][k][0] != INF || dp[i][i + 1][k][1] != INF)
ans = k;
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |