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
int n, len;
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 >> len;
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], len - 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({len-pos[n], {{n, n}, {1, (len - pos[n]) <= by[n]}}});
dp[1][1][0][pos[1] <= by[1]] = pos[1];
dp[n][n][1][(len - pos[n]) <= by[n]] = len - pos[n];
int lr = 0;
for (int isi=0; isi<=n; isi++) {
for (int l=1; l<=n; l++) {
int r = prev(((l - 1 + isi) % n) + 1);
for (int f=0; f<2; f++) {
for (int taken=0; taken<=n; taken++) {
if (dp[l][r][f][taken] == LLONG_MAX) continue;
int mtime = dp[l][r][f][taken];
lr = max(lr, taken);
int at = (f == 0 ? pos[l] : pos[r]);
if (can(l, r)) continue;
{
int before = prev(l);
int dist = abs(at - pos[before]);
int will = min(dist, len - dist) + mtime;
int ntaken = taken + (will <= by[before]);
dp[before][r][0][ntaken] = min(will, dp[before][r][0][ntaken]);
}
{
int after = next(r);
int dist = abs(at - pos[after]);
int will = min(dist, len - dist) + mtime;
int ntaken = taken + (will <= by[after]);
dp[l][after][1][ntaken] = min(will, dp[l][after][1][ntaken]);
}
}
}
}
}
cout << lr << endl;
}
# | 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... |