Approach
Sorting and greedy selection
For ABC461 C — Variety, 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
- 55 lines of Python from the credited upstream file abc461_c.py.
- The implementation visibly relies on sequence storage, hash lookup, ordered lookup.
- No explicit 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.
12 3 4def main():5 import sys6 from collections import defaultdict7 8 input = sys.stdin.readline9 10 n, k, m = map(int, input().split())11 pending = -112 c_max = [pending] * n13 d = defaultdict(list)14 15 for _ in range(n):16 ci, vi = map(int, input().split())17 ci -= 118 19 d[ci].append(vi)20 c_max[ci] = max(c_max[ci], vi)21 22 candidates = []23 24 for i, c_max_i in enumerate(c_max):25 if c_max_i == pending:26 continue27 28 candidates.append(c_max_i)29 30 candidates.sort(reverse=True)31 32 remains = []33 34 while len(candidates) > m:35 remains.append(candidates.pop())36 37 for key, values in d.items():38 values = sorted(values)39 values.pop()40 41 remains += values42 43 remains.sort()44 45 while len(candidates) < k:46 value = remains.pop()47 candidates.append(value)48 49 ans = sum(candidates)50 print(ans)51 52 53if __name__ == "__main__":54 main()55