結果

問題 No.2458 Line Up Charged Balls
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:57:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,667 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,092 KB
実行使用メモリ 153,476 KB
最終ジャッジ日時 2025-06-12 19:59:14
合計ジャッジ時間 14,074 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

n = int(input())
Q = list(map(int, input().split()))

if n == 2:
    print(Q[0] * Q[1])
    exit()

prev = [i-1 for i in range(n)]
next_ = [i+1 for i in range(n)]
active = [True] * n
gain = [0] * n

sum_E = 0
for i in range(n-1):
    sum_E += Q[i] * Q[i+1]

for i in range(1, n-1):
    p = prev[i]
    nxt = next_[i]
    if p == -1 or nxt == -1:
        gain[i] = 0
    else:
        gain[i] = Q[p] * Q[nxt] - (Q[p] * Q[i] + Q[i] * Q[nxt])

heap = []
for i in range(1, n-1):
    if gain[i] > 0:
        heapq.heappush(heap, (-gain[i], i, gain[i]))

removed = 0
max_removals = n - 2

while heap and removed < max_removals:
    neg_g, i, old_g = heapq.heappop(heap)
    current_g = gain[i]
    if not active[i] or current_g != old_g:
        continue
    active[i] = False
    sum_E += current_g
    removed += 1

    p = prev[i]
    nxt = next_[i]
    if p != -1:
        next_[p] = nxt
    if nxt != -1:
        prev[nxt] = p

    if p != -1 and p != 0:
        pp = prev[p]
        pn = next_[p]
        if pp == -1 or pn == -1:
            new_g = 0
        else:
            new_g = Q[pp] * Q[pn] - (Q[pp] * Q[p] + Q[p] * Q[pn])
        if new_g != gain[p]:
            gain[p] = new_g
            if new_g > 0:
                heapq.heappush(heap, (-new_g, p, new_g))

    if nxt != -1 and nxt != n - 1:
        np = prev[nxt]
        nn = next_[nxt]
        if np == -1 or nn == -1:
            new_g = 0
        else:
            new_g = Q[np] * Q[nn] - (Q[np] * Q[nxt] + Q[nxt] * Q[nn])
        if new_g != gain[nxt]:
            gain[nxt] = new_g
            if new_g > 0:
                heapq.heappush(heap, (-new_g, nxt, new_g))

print(sum_E)
0