Submission #1014624

#TimeUsernameProblemLanguageResultExecution timeMemory
1014624MilosMilutinovicShortcut (IOI16_shortcut)C++14
31 / 100
2017 ms2004 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; long long find_shortcut(int n, vector<int> l, vector<int> d, int c) { vector<long long> x(n); for (int i = 1; i < n; i++) { x[i] = x[i - 1] + l[i - 1]; } auto Check = [&](long long diam) { vector<array<long long, 3>> sq; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (d[i] + d[j] + x[j] - x[i] <= diam) { continue; } long long r = diam - d[i] - d[j] - c; if (r < 0) { return false; } sq.push_back({x[i], x[j], r}); } } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { bool ok = true; for (auto& p : sq) { if (abs(x[i] - p[0]) + abs(x[j] - p[1]) > p[2]) { ok = false; break; } } if (ok) { return true; } } } return false; }; long long low = 0, high = 1e18, ans = 0; while (low <= high) { long long mid = (low + high) >> 1; if (Check(mid)) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...