// moreflags=grader.cpp
// 16
#include "shortcut.h"
#include<vector>
#include<numeric>
#include<algorithm>
#include<cstdint>
#include<climits>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
std::vector<int64_t> pos; pos.reserve(n);
pos.push_back(0);
/*
pos.insert(pos.end(), begin(l), end(l));
std::partial_sum(++begin(pos), end(pos), ++pos.begin(), 0);
*/
std::inclusive_scan(begin(l), end(l), std::back_inserter(pos), std::plus<>(), (int64_t)0);
// it's very rare for C++ to have just the right built-in.
// Languages with better support for functional programming is better in this regard...
// (Rust, Kotlin (I think?), Haskell, Python (list comprehension, although it's more verbose),
// JavaScript (a little. Notably, integer range is missing), ...)
// Ranges v3 will be merged into C++ soon...
int64_t result{};
for(auto it: l) result+=it;
result+=2**std::max_element(begin(d), end(d));
l.clear();
auto const check=[&](int64_t const result){
std::array<int64_t, 4> bounds{{0, INT64_MAX, 0, INT64_MAX}};
// sum (minimum, maximum), difference (minimum, maximum)
for(int b=1; b<n; ++b)
for(int a=0; a<b; ++a){
auto const sum=pos[a]+pos[b], diff=pos[b]-pos[a];
assert(diff>0);
if(d[a]+d[b]+diff>result){
auto const rad=result-c-d[a]-d[b];
if(rad<0) return false;
bounds={{
std::max(bounds[0], sum-rad),
std::min(bounds[1], sum+rad),
std::max(bounds[2], diff-rad),
std::min(bounds[3], diff+rad)
}};
if(bounds[0]>bounds[1] or bounds[2]>bounds[3]) return false;
}
}
if(bounds[1]==INT64_MAX) return true; // no bound. (result >=old diameter?)
for(auto p: pos){
auto const l=std::max(bounds[0]-p, bounds[2]+p), r=std::min(bounds[1]-p, bounds[3]+p);
if(l<=r){
auto const iterator=std::lower_bound(begin(pos), end(pos), l);
if(iterator!=pos.end() and *iterator<=r)
return true; // found a point
}
}
return false;
};
for(int64_t step=(int64_t)1<<(63^__builtin_clzll(result)); step; step>>=1)
if(result-step>0 and check(result-step))
result-=step;
return result;
}
