#include <bits/stdc++.h>
using namespace std;
struct Artifact {
int weight;
int cost_alone;
int cost_pair;
};
bool cmp_by_weight(const Artifact &a, const Artifact &b) {
return a.weight < b.weight;
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int N = W.size();
int Q = E.size();
vector<vector<Artifact>> weight_buckets(11);
for (int i = 0; i < N; ++i) {
weight_buckets[W[i]].push_back({W[i], A[i], B[i]});
}
for (int w = 1; w <= 10; ++w) {
sort(weight_buckets[w].begin(), weight_buckets[w].end(), [](const Artifact &a, const Artifact &b) {
return a.cost_alone - a.cost_pair > b.cost_alone - b.cost_pair;
});
}
vector<long long> answers;
for (int d : E) {
vector<Artifact> candidates;
for (int w1 = 1; w1 <= 10; ++w1) {
for (int w2 = max(1, w1 - d); w2 <= min(10, w1 + d); ++w2) {
if (w1 <= w2) {
for (auto &a : weight_buckets[w1]) {
candidates.push_back(a);
}
if (w1 != w2) {
for (auto &b : weight_buckets[w2]) {
candidates.push_back(b);
}
}
}
}
}
sort(candidates.begin(), candidates.end(), cmp_by_weight);
vector<bool> used(candidates.size(), false);
long long total_cost = 0;
for (int i = 0; i < candidates.size(); ++i) {
if (used[i]) continue;
int j = i + 1;
while (j < candidates.size() && (used[j] || abs(candidates[i].weight - candidates[j].weight) > d)) {
++j;
}
if (j < candidates.size()) {
used[i] = used[j] = true;
total_cost += candidates[i].cost_pair + candidates[j].cost_pair;
}
}
for (int i = 0; i < candidates.size(); ++i) {
if (!used[i]) total_cost += candidates[i].cost_alone;
}
answers.push_back(total_cost);
}
return answers;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |