Approach
Sorting and greedy selection
For ABC358 D — Souvenirs, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 63 lines of C++ from the credited upstream file abc358_d.cpp.
- The implementation visibly relies on sequence storage, ordered lookup.
- 4 loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1#include <algorithm>2#include <iostream>3#include <map>4#include <vector>5 6using namespace std;7using ui = unsigned int;8using ull = unsigned long long;9 10int main() {11 ui n, m;12 cin >> n >> m;13 14 map<ui, ui> box;15 for (ui i = 0; i < n; i++) {16 ui a;17 cin >> a;18 box[a]++;19 }20 21 vector<ui> bb(m, 0);22 for (auto& b : bb) cin >> b;23 24 sort(bb.begin(), bb.end());25 26 ull ans = 0;27 for (auto& b : bb) {28 bool ok = false;29 ui cb = b;30 if (box.count(b) > 0) {31 ok = true;32 } else {33 auto it = box.begin();34 while (it != box.end()) {35 if (b > it->first) {36 ui er = it->first;37 it++;38 box.erase(er);39 if (box.size() == 0) break;40 continue;41 }42 43 cb = it->first;44 ok = true;45 break;46 }47 }48 49 if (!ok) {50 cout << -1 << endl;51 return 0;52 }53 54 ans += ull(cb);55 box[cb]--;56 57 if (box[cb] == 0) box.erase(cb);58 }59 60 cout << ans << endl;61 62 return 0;63}