# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
295871 | dCoding | Gap (APIO16_gap) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void MinMax(ll s, ll t, ll& a, ll& b);
ll findGap(int t, int n) {
ll lo = 0, hi = 1e18;
vector<ll> l,h;
ll mn = 0,mx = 0;
while(l.size()+h.size() < n) {
MinMax(lo,hi,&mn,&mx);
if(mn == mx) {
l.push_back(mn);
} else {
l.push_back(mn);
h.push_back(mx);
}
lo = mn;
hi = mx;
}
ll ans = 0;
for(int i=1;i<l.size();i++) ans = max(ans, l[i]-l[i-1]);
for(int i=1;i<h.size();i++) ans = max(ans, h[i]-h[i-1]);
ans = max(ans, h[0]-l.back());
return ans;
}