Submission #286176

#TimeUsernameProblemLanguageResultExecution timeMemory
286176reymontada61Collecting Stamps 3 (JOI20_ho_t3)C++14
15 / 100
2092 ms145076 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...