結果

問題 No.1150 シュークリームゲーム（Easy）
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:43:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,876 bytes
コンパイル時間 309 ms
コンパイル使用メモリ 81,980 KB
実行使用メモリ 105,012 KB
最終ジャッジ日時 2025-06-12 19:44:02
合計ジャッジ時間 5,629 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 16 WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    s = int(data[idx])
    t = int(data[idx+1])
    idx +=2
    a = list(map(int, data[idx:idx+N]))
    idx += N
    
    # Build adjacency list
    adj = [[] for _ in range(N+1)]
    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] = [prev, next_]
    
    visited = [0] * (N+1)
    visited[s] = 1
    visited[t] = 2
    
    X = a[s-1]
    Y = a[t-1]
    
    # Initialize heaps
    heap1 = []
    for u in adj[s]:
        if visited[u] == 0:
            heapq.heappush(heap1, (-a[u-1], u))
    
    heap2 = []
    for u in adj[t]:
        if visited[u] == 0:
            heapq.heappush(heap2, (-a[u-1], u))
    
    while True:
        # Player 1's turn
        moved1 = False
        while heap1:
            current = heapq.heappop(heap1)
            a_val = -current[0]
            u = current[1]
            if visited[u] != 0:
                continue
            visited[u] = 1
            X += a[u-1]
            for v in adj[u]:
                if visited[v] == 0:
                    heapq.heappush(heap1, (-a[v-1], v))
            moved1 = True
            break
        if not moved1:
            break
        
        # Player 2's turn
        moved2 = False
        while heap2:
            current = heapq.heappop(heap2)
            a_val = -current[0]
            u = current[1]
            if visited[u] != 0:
                continue
            visited[u] = 2
            Y += a[u-1]
            for v in adj[u]:
                if visited[v] == 0:
                    heapq.heappush(heap2, (-a[v-1], v))
            moved2 = True
            break
        if not moved2:
            break
    
    print(X - Y)

if __name__ == "__main__":
    main()
0