Approach
Sorting and greedy selection
For ABC315 C — Flavors, 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
- 45 lines of C++ from the credited upstream file abc315_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 ul = unsigned long;9 10struct Ice {11 ui f;12 ul s;13};14 15bool comp(Ice& l, Ice& r) { return l.s < r.s; }16 17int main() {18 ui n;19 cin >> n;20 21 vector<Ice> cups(n);22 for (auto& ice : cups) {23 ui f;24 ul s;25 cin >> f >> s;26 ice.f = f;27 ice.s = s;28 }29 30 sort(cups.rbegin(), cups.rend(), comp);31 32 ul ans = 0;33 ans = cups[0].s + cups[1].s;34 if (cups[0].f == cups[1].f) {35 ans -= cups[1].s / 2;36 for (ui i = 2; i < n; i++) {37 if (cups[0].f != cups[i].f) {38 ans = max(ans, cups[0].s + cups[i].s);39 break;40 }41 }42 }43 44 cout << ans << endl;45}