- Define the priority key and whether the smallest or largest item should lead.
- Push each candidate when it becomes eligible.
- Discard stale entries when necessary and process the best live candidate.
Code notes
- 56 lines of Python from the credited upstream file abc384_e.py.
- The implementation visibly relies on sequence storage, ordered lookup, work queue.
- No explicit loop blocks detected.
Complexity
Count heap pushes and pops; each normally contributes a logarithmic factor in the heap size.
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 heapq import heappop, heappush7 8 input = sys.stdin.readline9 10 h, w, z = map(int, input().split())11 p, q = map(int, input().split())12 p -= 113 q -= 114 s = [list(map(int, input().split())) for _ in range(h)]15 16 dxy = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (1, -1), (-1, 1), (1, 1)]17 dxy = dxy[:4]18 heap = []19 ans = s[p][q]20 added = [[False] * w for _ in range(h)]21 added[p][q] = True22 23 def f(cur_y, cur_x):24 for dx, dy in dxy:25 ny = cur_y + dy26 nx = cur_x + dx27 28 if not (0 <= ny < h):29 continue30 if not (0 <= nx < w):31 continue32 33 if added[ny][nx]:34 continue35 36 heappush(heap, (s[ny][nx], ny, nx))37 added[ny][nx] = True38 39 f(p, q)40 41 while heap:42 score, cur_y, cur_x = heap[0]43 44 if score * z >= ans:45 break46 47 ans += score48 heappop(heap)49 f(cur_y, cur_x)50 51 print(ans)52 53 54if __name__ == "__main__":55 main()56