結果

問題 No.1906 Twinkle Town
ユーザー hitonanode
提出日時 2022-02-05 14:11:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 217 ms / 2,000 ms
コード長 639 bytes
コンパイル時間 279 ms
コンパイル使用メモリ 82,564 KB
実行使用メモリ 102,340 KB
最終ジャッジ日時 2024-06-22 04:05:15
合計ジャッジ時間 12,421 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 想定解
# Python3 でも通る（なんならそっちの方が速い）んですが、シンプル軽実装がバレるので、PyPy にします
import heapq


def solve() -> int:
    N, A = int(input()), sorted(map(int, input().split()))

    heap = list()
    ret, latest_a = 0, 0

    for i, a in enumerate(A):
        heapq.heappush(heap, -(a - latest_a))  # 大きいものから取り出したいので符号反転させて入れる
        latest_a = a
        if i % 2 == 0:
            ret -= heapq.heappop(heap)

    return ret if N % 2 else A[-1] - ret


ret = [solve() for _ in range(int(input()))]
print(*ret, sep='\n')
0