結果

問題 No.1150 シュークリームゲーム（Easy）
ユーザー gew1fw
提出日時 2025-06-12 19:39:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,067 bytes
コンパイル時間 204 ms
コンパイル使用メモリ 81,972 KB
実行使用メモリ 103,104 KB
最終ジャッジ日時 2025-06-12 19:39:38
合計ジャッジ時間 5,734 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 WA * 10 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    s = int(data[1])
    t = int(data[2])
    a = list(map(int, data[3:3+n]))
    
    a = [0] + a  # 转换为1-based索引
    
    belong = [0] * (n + 1)
    belong[s] = 1
    belong[t] = 2
    
    heap_315 = []
    heap_8128 = []
    
    def get_neighbors(i):
        left = i - 1
        if left < 1:
            left = n
        right = i + 1
        if right > n:
            right = 1
        return left, right
    
    s_left, s_right = get_neighbors(s)
    for u in [s_left, s_right]:
        if belong[u] == 0:
            heapq.heappush(heap_315, (-a[u], u))
    
    t_left, t_right = get_neighbors(t)
    for u in [t_left, t_right]:
        if belong[u] == 0:
            heapq.heappush(heap_8128, (-a[u], u))
    
    X = a[s]
    Y = a[t]
    
    while True:
        # 315回合
        moved = False
        while heap_315:
            val, u = heapq.heappop(heap_315)
            if belong[u] == 0:
                belong[u] = 1
                X += a[u]
                left, right = get_neighbors(u)
                for v in [left, right]:
                    if belong[v] == 0:
                        heapq.heappush(heap_315, (-a[v], v))
                moved = True
                break
        if not moved and not heap_8128:
            break
        
        # 8128回合
        moved = False
        while heap_8128:
            val, u = heapq.heappop(heap_8128)
            if belong[u] == 0:
                belong[u] = 2
                Y += a[u]
                left, right = get_neighbors(u)
                for v in [left, right]:
                    if belong[v] == 0:
                        heapq.heappush(heap_8128, (-a[v], v))
                moved = True
                break
        if not moved and not heap_315:
            break
        
        # 检查是否所有顶点都被分配
        if sum(belong) == n + 1:
            break
    
    print(X - Y)

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