Approach
Sorting and greedy selection
For ABC229 C — Cheese, 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
- 42 lines of C++ from the credited upstream file abc229_c.cpp.
- The implementation visibly relies on sequence storage.
- 2 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 <cmath>3#include <iostream>4#include <vector>5 6using namespace std;7using ui = unsigned int;8using ull = unsigned long long;9 10bool comp(pair<ull, ull>& l, pair<ull, ull>& r) {11 if (l.first != r.first) return l.first > r.first;12 13 return l.second > r.second;14}15 16int main() {17 ui n;18 ull w;19 cin >> n >> w;20 21 vector<pair<ull, ull>> ab(n);22 for (auto& c : ab) cin >> c.first >> c.second;23 24 sort(ab.begin(), ab.end(), comp);25 26 ull ans = 0;27 for (auto& c : ab) {28 if (w >= c.second) {29 ans += c.first * c.second;30 w -= c.second;31 } else {32 ans += c.first * w;33 w = 0;34 }35 36 if (w == 0) break;37 }38 39 cout << ans << endl;40 41 return 0;42}