Approach
Sorting and greedy selection
For ABC181 E — Transformable Teacher, 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 Python from the credited upstream file abc181_e.py.
- The implementation visibly relies on sequence storage, 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 from bisect import bisect_right6 import sys7 8 input = sys.stdin.readline9 10 n, m = map(int, input().split())11 h = sorted(list(map(int, input().split())))12 w = list(map(int, input().split()))13 14 summed_h = [0 for _ in range(n + 1)]15 16 for index, hi in enumerate(h, 1):17 if index % 2 == 1:18 summed_h[index] -= hi19 else:20 summed_h[index] += hi21 22 summed_h[index] += summed_h[index - 1]23 24 ans = float("Inf")25 26 for wi in w:27 index = bisect_right(h, wi)28 29 if index % 2 == 0:30 flag = -131 else:32 flag = 133 34 total = summed_h[index]35 total += flag * wi36 total -= summed_h[n] - summed_h[index]37 38 ans = min(ans, total)39 40 print(ans)41 42 43if __name__ == "__main__":44 main()45