#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 9e18;
struct Artifact {
ll w;
ll a;
ll b;
};
const ll MAX_SZ = 1e5 + 10;
ll memo[MAX_SZ];
ll dp(ll D, vector<Artifact> &artifacts) {
memset(memo, -1LL, sizeof(memo));
ll N = (ll)artifacts.size();
memo[N] = 0;
ll dPointer = N - 1;
set<pair<ll, ll> > res2Selection;
map<ll, pair<ll, ll> > toRemove;
ll accumInd = N;
ll accum = 0;
for (ll ind = N - 1; ind >= 0; ind--) {
if (ind < N - 1) accum += artifacts[ind].a;
// cout << "accum(" << ind << "): " << accum << endl;
// res1: keep single
ll res1 = memo[ind + 1] + artifacts[ind].a;
// remove stuff you cannot pair-up
while (artifacts[dPointer].w - artifacts[ind].w > D) {
res2Selection.erase(toRemove[dPointer]);
dPointer--;
}
// cout << "currentInd (" << ind << "): ";
// for (auto l: res2Selection) {
// cout << l.first << ", " << l.second << "; ";
// }
// cout << endl;
// cout << "----" << endl;
if (res2Selection.size() == 0) { // nothing to pair-up
res2Selection.insert({memo[ind + 1] + artifacts[ind].b - accum, ind});
toRemove[ind] = {memo[ind + 1] + artifacts[ind].b - accum, ind};
memo[ind] = res1;
continue;
}
// res2: pair-up with best DP
pair<ll, ll> bestPair = *res2Selection.begin();
ll res2 = artifacts[ind].b + bestPair.first + accum - artifacts[ind].a;
res2Selection.insert({memo[ind + 1] + artifacts[ind].b - accum, ind});
toRemove[ind] = {memo[ind + 1] + artifacts[ind].b - accum, ind};
memo[ind] = min(res1, res2);
}
// for (ll i = 0; i <= N; i++) {
// cout << memo[i] << ", ";
// }
// cout << endl;
return memo[0];
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
ll Q = (ll)E.size();
ll N = (ll)A.size();
vector<ll> R(Q);
vector<Artifact> artifacts;
artifacts.reserve(N);
for (ll i = 0; i < N; i++) {
artifacts.push_back(Artifact{W[i], A[i], B[i]});
}
sort(artifacts.begin(), artifacts.end(), [&](Artifact &a, Artifact &b) {
if (a.w == b.w) {
if (a.a == b.a) {
return a.b < b.b;
}
return a.a < b.a;
}
return a.w < b.w;
});
for (ll queryInd = 0; queryInd < Q; queryInd++) {
ll res = dp(E[queryInd], artifacts);
R[queryInd] = res;
}
return R;
}
