Submission #1244429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244429		im2xtreme	Nile (IOI24_nile)	C++20	0 / 100	19 ms	3080 KiB

nile

#include <bits/stdc++.h>
#include "nile.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;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18