- 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
- 130 lines of Python from the credited upstream file abc267_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 4import heapq5 6 789class Heapq:10 def __init__(self, hq = [], descending_order = False):11 if descending_order:12 self.sign = -113 self.hq = [-l for l in hq]14 else:15 self.sign = 116 self.hq = hq[:]17 18 heapq.heapify(self.hq)19 self.total = sum(hq)20 self.count = {}21 22 for l in hq:23 self.count[l] = self.count.get(l, 0) + 124 25 self.length = len(hq)26 27 def __bool__(self):28 return self.length > 029 30 def __len__(self):31 return self.length32 33 def __getitem__(self, i):34 if i == 0:35 return self.top()36 else:37 assert False38 39 def push(self, x):40 self.length += 141 self.count[x * self.sign] = self.count.get(x * self.sign, 0) + 142 heapq.heappush(self.hq, x * self.sign)43 self.total += x44 45 def pop(self):46 if self.length == 0:47 return None48 49 self.length -= 150 result = heapq.heappop(self.hq)51 self.total -= self.sign * result52 self.count[result] -= 153 self.delete()54 55 return self.sign * result56 57 def top(self):58 if self.hq:59 return self.sign * self.hq[0]60 else:61 return None62 63 def remove(self, x):64 if self.count.get(x * self.sign, 0) == 0:65 return False66 67 self.count[x * self.sign] -= 168 self.length -= 169 self.total -= x70 self.delete()71 72 return True73 74 def delete(self):75 while self.hq and self.count.get(self.hq[0], 0) == 0:76 heapq.heappop(self.hq)77 78 79def main():80 import sys81 82 input = sys.stdin.readline83 84 n, m = map(int, input().split())85 a = list(map(int, input().split()))86 graph = [[] for _ in range(n)]87 88 for _ in range(m):89 ai, bi = map(int, input().split())90 ai -= 191 bi -= 192 93 graph[ai].append(bi)94 graph[bi].append(ai)95 96 costs = [0] * n97 hq = Heapq()98 99 for i in range(n):100 for to in graph[i]:101 costs[i] += a[to]102 103 104 105 for i, cost in enumerate(costs):106 hq.push(cost * n + i)107 108 used = [False] * n109 ans = 0110 111 while hq:112 cost, v = divmod(hq.pop(), n)113 114 used[v] = True115 ans = max(ans, cost)116 117 for to in graph[v]:118 if used[to]:119 continue120 121 hq.remove(costs[to] * n + to)122 costs[to] -= a[v]123 hq.push(costs[to] * n + to)124 125 print(ans)126 127 128if __name__ == "__main__":129 main()130