結果

問題 No.1150 シュークリームゲーム（Easy）
ユーザー qwewe
提出日時 2025-04-24 12:20:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,691 bytes
コンパイル時間 295 ms
コンパイル使用メモリ 82,268 KB
実行使用メモリ 97,912 KB
最終ジャッジ日時 2025-04-24 12:21:53
合計ジャッジ時間 5,720 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 16 WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

N = int(input())
s, t = map(int, input().split())
A = list(map(int, input().split()))

# Initialize adjacency list for each vertex
adj = [[] for _ in range(N + 1)]  # 1-based indexing
for i in range(1, N + 1):
    prev = i - 1 if i > 1 else N
    next_ = i + 1 if i < N else 1
    adj[i].append(prev)
    adj[i].append(next_)

visited = [False] * (N + 1)
visited[s] = True
visited[t] = True

X = A[s - 1]
Y = A[t - 1]

# Priority queues for both players (using max-heap simulation with negative values)
heap315 = []
heap8128 = []

# Initialize heaps with adjacent vertices of s and t
for u in adj[s]:
    if not visited[u]:
        heapq.heappush(heap315, (-A[u - 1], u))

for u in adj[t]:
    if not visited[u]:
        heapq.heappush(heap8128, (-A[u - 1], u))

turn = 0  # 0 for 315's turn, 1 for 8128's turn

while heap315 or heap8128:
    if turn == 0:
        if not heap315:
            turn = 1
            continue
        val, u = heapq.heappop(heap315)
        current_A = -val
        if visited[u]:
            continue
        visited[u] = True
        X += current_A
        # Add adjacent vertices to the heap
        for v in adj[u]:
            if not visited[v]:
                heapq.heappush(heap315, (-A[v - 1], v))
        turn = 1
    else:
        if not heap8128:
            turn = 0
            continue
        val, u = heapq.heappop(heap8128)
        current_A = -val
        if visited[u]:
            continue
        visited[u] = True
        Y += current_A
        # Add adjacent vertices to the heap
        for v in adj[u]:
            if not visited[v]:
                heapq.heappush(heap8128, (-A[v - 1], v))
        turn = 0

print(X - Y)
0