結果
問題 |
No.838 Noelちゃんと星々3
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:33:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 1,040 bytes |
コンパイル時間 | 192 ms |
コンパイル使用メモリ | 82,284 KB |
実行使用メモリ | 91,364 KB |
最終ジャッジ日時 | 2025-03-31 17:34:37 |
合計ジャッジ時間 | 2,612 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
import sys n = int(sys.stdin.readline()) Y = list(map(int, sys.stdin.readline().split())) Y.sort() prefix_sum = [0] * (n + 1) for i in range(n): prefix_sum[i + 1] = prefix_sum[i] + Y[i] INF = float('inf') dp = [INF] * (n + 1) dp[0] = 0 for i in range(1, n + 1): # Check for group of size 2 if i >= 2: left = i - 2 right = i - 1 m = (right - left) // 2 + left sum_left = (m - left + 1) * Y[m] - (prefix_sum[m + 1] - prefix_sum[left]) sum_right = (prefix_sum[right + 1] - prefix_sum[m + 1]) - (right - m) * Y[m] cost = sum_left + sum_right dp[i] = min(dp[i], dp[left] + cost) # Check for group of size 3 if i >= 3: left = i - 3 right = i - 1 m = (right - left) // 2 + left sum_left = (m - left + 1) * Y[m] - (prefix_sum[m + 1] - prefix_sum[left]) sum_right = (prefix_sum[right + 1] - prefix_sum[m + 1]) - (right - m) * Y[m] cost = sum_left + sum_right dp[i] = min(dp[i], dp[left] + cost) print(int(dp[n]))