Submission #1232551

#TimeUsernameProblemLanguageResultExecution timeMemory
1232551nibertNile (IOI24_nile)C++20
0 / 100
17 ms2624 KiB
#include "bits/stdc++.h" #include "nile.h" using namespace std; vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) { const int MAX_W = 10; const int MAX_D = 10; int N = W.size(), Q = E.size(); // Group artifacts by weight vector<vector<pair<int, int>>> by_weight(MAX_W + 1); // weight -> list of (A-B, B) for (int i = 0; i < N; ++i) { int w = W[i]; by_weight[w].emplace_back(A[i] - B[i], B[i]); } // Precompute total cost for each D in [1, 10] vector<long long> cost_for_d(MAX_D + 1, 0); for (int D = 1; D <= MAX_D; ++D) { // Copy and sort the weight groups vector<multiset<pair<int, int>>> sets(MAX_W + 1); for (int w = 1; w <= MAX_W; ++w) { for (auto p : by_weight[w]) sets[w].insert(p); } long long total = 0; // Try to pair items within W[w] and W[w'] for (int w = 1; w <= MAX_W; ++w) { for (int dw = 0; dw <= D; ++dw) { int w2 = w + dw; if (w2 > MAX_W) continue; while (sets[w].size() && sets[w2].size()) { if (w == w2 && sets[w].size() < 2) break; if (w == w2) { // Same group pairing: need two elements auto it1 = sets[w].begin(); auto it2 = next(it1); total += it1->second + it2->second; // B[i] + B[j] sets[w].erase(it1); sets[w].erase(sets[w].begin()); } else { auto it1 = sets[w].begin(); auto it2 = sets[w2].begin(); total += it1->second + it2->second; sets[w].erase(it1); sets[w2].erase(it2); } } } } // Now send remaining unpaired items alone for (int w = 1; w <= MAX_W; ++w) { for (auto [extra, b] : sets[w]) { total += b + extra; // B[i] + (A[i] - B[i]) = A[i] } } cost_for_d[D] = total; } // Answer queries vector<long long> result(Q); for (int i = 0; i < Q; ++i) { result[i] = cost_for_d[E[i]]; } return result; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...