Submission #958951

#TimeUsernameProblemLanguageResultExecution timeMemory
958951MinaRagy06Shortcut (IOI16_shortcut)C++17
71 / 100
2025 ms2516 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #include "shortcut.h" #ifdef MINA #include "grader.cpp" #endif using namespace std; #define ll long long const int N = 3005; ll find_shortcut(int n, vector<int> l, vector<int> a, int c) { reverse(l.begin(), l.end()), l.push_back(0), reverse(l.begin(), l.end()), l.push_back(0); reverse(a.begin(), a.end()), a.push_back(-1), reverse(a.begin(), a.end()); ll prf[n + 2]{}; for (int i = 2; i <= n; i++) { prf[i] = prf[i - 1] + l[i - 1]; } ll s[n + 2]{}, d[n + 2]{}; for (int i = 1; i <= n; i++) { s[i] = prf[i] + a[i]; d[i] = prf[i] - a[i]; } auto check = [&] (ll t) { ll l1 = -1e18, r1 = 1e18, l2 = -1e18, r2 = 1e18; for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { if (i == j) continue; if (prf[j] - prf[i] + a[i] + a[j] > t) { l1 = max(l1, s[i] + s[j] - t + c); r1 = min(r1, d[i] + d[j] + t - c); l2 = max(l2, - d[i] + s[j] - t + c); r2 = min(r2, - s[i] + d[j] + t - c); } } } for (int x = 1; x <= n; x++) { ll st = max(l1 - prf[x], l2 + prf[x]); ll en = min(r1 - prf[x], r2 + prf[x]); for (int y = 1; y <= n; y++) { if (st <= prf[y] && prf[y] <= en) { return true; } } } return false; }; ll st = 0, en = 1ll << 41; while (st <= en) { ll md = (st + en) >> 1; if (check(md)) { en = md - 1; } else { st = md + 1; } } return st; }
#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...