| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 281991 | 2020-08-23T18:32:07 Z | theStaticMind | Shortcut (IOI16_shortcut) | C++14 | 0 ms | 0 KB |
#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));
}
}
}
return x1 <= x2 && y1 <= y2;
}
int64_t 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;
}