# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
99952 | 2019-03-08T22:06:38 Z | MvC | Shortcut (IOI16_shortcut) | C++11 | 0 ms | 0 KB |
#include "shortcut.h" #include<bits/stdc++.h> using namespace std; #define ll long long const int maxn = 3000 + 5; const ll inf = 1e15; int n; ll cost, len[maxn], val[maxn]; ll pos[maxn]; bool check(ll k) { // printf("check %lld\n",k); ll r1 = -inf, r2 = inf, c1 = -inf, c2 = inf; for(int x=0;x<n;x++) { for(int y=x+1;y<n;y++) { if(val[x] + val[y] + pos[y] - pos[x] <= k) continue; ll d = k - cost - val[x] - val[y]; r1 = max(r1, pos[x] + pos[y] - d); c1 = max(c1, -pos[x] + pos[y] - d); r2 = min(r2, pos[x] + pos[y] + d); c2 = min(c2, -pos[x] + pos[y] + d); } } for(int x=0;x<n;x++) { for(int y=x+1;y<n;y++) { ll r = (pos[x]+pos[y]), c = (-pos[x]+pos[y]); if(r1 <= r && r <= r2 && c1 <= c && c <= c2) return 1; } } return 0; } ll find_shortcut(int N, vector<int> l, vector<int> d, int c) { n = N; cost = c; for(int i=0;i<n-1;i++) len[i] = l[i]; for(int i=0;i<n;i++) val[i] = d[i]; for(int i=0;i<n-1;i++) pos[i+1] = pos[i] + len[i]; ll l = 0, r = inf, mid, res = -1; while(l<=r) { mid = (l+r)/2; if(check(mid)) { res = mid; r = mid-1; } else l = mid+1; } return res; }