Submission #282002

#TimeUsernameProblemLanguageResultExecution timeMemory
282002theStaticMindShortcut (IOI16_shortcut)C++14
71 / 100
2075 ms2296 KiB
#include<bits/stdc++.h> #define pb push_back #define ii pair<int,int> #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define INF 100000000000000000 #define modulo 1000000007 #define mod 998244353 using namespace std; #include "shortcut.h" int64_t n, c; vector<int64_t> d; vector<int64_t> p; bool ok(int64_t k){ int64_t x1 = -1e18, x2 = 1e18, y1 = -1e18, y2 = 1e18; for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ if(d[i] + d[j] + p[j] - p[i] > k){ x1 = max(x1, p[i] + p[j] - (k - d[i] - d[j] - c)); x2 = min(x2, p[i] + p[j] + (k - d[i] - d[j] - c)); y1 = max(y1, p[j] - p[i] - (k - d[i] - d[j] - c)); y2 = min(y2, p[j] - p[i] + (k - d[i] - d[j] - c)); } } } for(int x = 0; x < n; x++){ for(int y = 0; y < n; y++){ int64_t a = p[x] + p[y]; int64_t b = p[y] - p[x]; if(x1 <= a && a <= x2 && y1 <= b && b <= y2) return true; } } return false; } long long find_shortcut(int N, std::vector<int> l, std::vector<int> D, int C){ n = N; c = C; for(auto x : D) d.pb(x); p = vector<int64_t>(n, 0); for(int i = 1; i < n; i++) p[i] = p[i - 1] + l[i - 1]; int64_t a = 0, b = 1e18, ans = 1e18; while(a <= b){ int64_t m = (a + b) / 2; if(ok(m)){ ans = m; b = m - 1; } else a = m + 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...