Approach
Sorting and greedy selection
For ABC195 D — Shipping Center, 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 abc195_d.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 import sys6 7 input = sys.stdin.readline8 9 n, m, q = map(int, input().split())10 wv = sorted([tuple(map(int, input().split())) for _ in range(n)])11 x = list(map(int, input().split()))12 13 for qi in range(q):14 li, ri = map(int, input().split())15 li -= 116 ri -= 117 18 boxes = list()19 20 for i in range(m):21 if li <= i <= ri:22 continue23 24 boxes.append(x[i])25 26 boxes = sorted(boxes)27 is_used = [False for _ in range(n)]28 ans = 029 30 for box in boxes:31 best_value, index = -1, -132 33 for i in range(n):34 if is_used[i]:35 continue36 37 if wv[i][0] > box:38 continue39 40 if wv[i][1] > best_value:41 best_value = wv[i][1]42 index = i43 44 if index == -1:45 continue46 47 is_used[index] = True48 ans += wv[index][1]49 50 print(ans)51 52 53if __name__ == "__main__":54 main()55