#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// Base printer for general types
template<typename T>
void __print(const T& x) {
cerr << x;
}
// Specialized printer for string
void __print(const string& x) { cerr << '"' << x << '"'; }
void __print(const char* x) { cerr << '"' << x << '"'; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
// Specialized printer for pair
template<typename T1, typename T2>
void __print(const pair<T1, T2>& p) {
cerr << "(";
__print(p.first);
cerr << ", ";
__print(p.second);
cerr << ")";
}
// For containers: vector, set, map, etc. (but not string or pair)
template<typename T, typename = void>
struct is_container : false_type {};
template<typename T>
struct is_container<T, std::void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>> : true_type {};
template<typename T>
typename enable_if<is_container<T>::value && !is_same<T, string>::value, void>::type
__print(const T& container) {
cerr << "{";
bool first = true;
for (const auto& item : container) {
if (!first) cerr << ", ";
__print(item);
first = false;
}
cerr << "}";
}
// Recursive variadic template debug printer
template<typename T>
void _debug_cerr(const char* name, T&& value) {
cerr << name << ": ";
__print(value);
cerr << '\n';
}
template<typename T, typename... Args>
void _debug_cerr(const char* names, T&& value, Args&&... args) {
const char* comma = strchr(names, ',');
cerr.write(names, comma - names) << ": ";
__print(value);
cerr << ", ";
_debug_cerr(comma + 1, forward<Args>(args)...);
}
// Macro interface
#define debug(...) _debug_cerr(#__VA_ARGS__, __VA_ARGS__)
vector<pair<int ,int>> w; // first int is size, second is the index it is
vector<int> diff;
vector<ll> pref;
// returns the maximum amount that can me saved in a range
ll find_min(int l, int r, int eval)
{
debug(l, r, eval);
ll region_tot = (l == 0) ? pref[r] : pref[r] - pref[l - 1];
if((r - l + 1 ) % 2 == 0)
{
return region_tot;
}
// odd amount of things can't take all
ll ans = 0;
for(int i = l; i <= r; i ++)
{
if((i - l) % 2 == 0)// if your position is - l is even
{
// then you can take everything minus your current place
ans = max(ans, region_tot - diff[i]);
}
else
{
if(abs(w[i-1].first - w[i+1].first) <=eval)
{
ans = max(ans, region_tot - diff[i]);
}
}
// we consider pure odd case to be always worse than even case
}
return ans;
}
vector<ll> calculate_costs(vector<int> W, vector<int> A,vector<int> B, vector<int> E)
{
int Q = (int)E.size();
vector<ll> R(Q, 0);
ll total_cost = 0;
int n = (int) W.size();
diff = vector<int>(n, 0);
pref = vector<ll>(n, 0);
vector<pair<int, int>> e; // first is D[i], second is index
vector<int> segment_end(n, 0);
for(int i = 0; i < n; i ++)
{
total_cost += A[i];
w.push_back({W[i], i});
segment_end[i] = i;
}
sort(w.begin(), w.end());
for(int i = 0 ; i< Q; i ++)
{
e.push_back({E[i], i});
}
sort(e.begin(), e.end());
for(int i = 0; i < n; i ++)
{
diff[i] = A[w[i].second] - B[w[i].second];
(i !=0) ? pref[i] = pref[i-1] + diff[i] : pref[i] = diff[i];
}
for(auto eval: e)
{
debug(eval);
ll ans = total_cost;
debug(total_cost);
int range_begin = 0;
int range_end = 0;
for(int i = 0; i < n-1; i ++)
{
if(abs(w[i].first - w[i+1].first) <= eval.first)
{
range_end = i + 1;
}
else
{
ll temp = find_min(range_begin, range_end, eval.first);
ans -= temp;
debug(temp);
range_begin = range_end = i + 1;
}
}
ll temp = find_min(range_begin, range_end, eval.first);
debug(temp);
ans -= temp; // the off by one end needs to also be done
R[eval.second] = ans;
}
return R;
}
