結果

問題 No.2458 Line Up Charged Balls
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:33:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 566 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 137,480 KB
最終ジャッジ日時 2025-03-31 17:33:49
合計ジャッジ時間 4,082 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

# Compute the original sum S
S = 0
for i in range(n - 1):
    S += q[i] * q[i + 1]

# Compute the gains for each possible removable position
gains = []
for i in range(1, n - 1):
    left = q[i - 1]
    right_val = q[i + 1]
    current = q[i]
    gain = left * right_val - current * (left + right_val)
    if gain > 0:
        gains.append(gain)

# Solve the maximum independent set problem (House Robber)
prev, curr = 0, 0
for g in gains:
    new = max(curr, prev + g)
    prev, curr = curr, new

print(S + curr)
0