#include "nile.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
struct Artifact {
int weight;
int cost;
};
vector<Artifact> artifacts;
vector<bool> cached;
vector<long long> memo;
long long dp(const int max_allowed_weight_dif, int i) {
if (i < 0)
return 0;
long long& res = memo[i];
if (!cached[i]) {
// ship artifact[i] by itself
res = artifacts[i].cost + dp(max_allowed_weight_dif, i-1);
// match with artifact[i-1]
if (i >= 1 and artifacts[i].weight - artifacts[i-1].weight <= max_allowed_weight_dif) {
res = min(res, dp(max_allowed_weight_dif, i-2));
}
// match with artifact[i-2] and ship artifact[i-1] by itself
if (i >= 2 and artifacts[i].weight - artifacts[i-2].weight <= max_allowed_weight_dif) {
res = min(res, artifacts[i-1].cost + dp(max_allowed_weight_dif, i-3));
}
cached[i] = true;
}
return res;
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B,
vector<int> E) {
// subtask 5: Q <= 5
const int N = W.size();
if (N == 1)
return vector<long long>(N, A[0]);
long long base_cost = 0;
for (int i = 0; i < N; i++)
base_cost += B[i];
// cerr << "base_cost: " << base_cost << endl;
const int Q = E.size();
vector<long long> R(Q, base_cost);
artifacts.clear();
for (int i = 0; i < N; i++)
artifacts.push_back({W[i], A[i] - B[i]});
sort(artifacts.begin(), artifacts.end(),
[&] (Artifact a, Artifact b) -> bool {return a.weight < b.weight; });
for (int j = 0; j < Q; j++) {
int e = E[j];
cached.assign(N, false);
memo.assign(N, -1);
R[j] += dp(e, N-1);
}
return R;
}
