結果
問題 | No.1391 ±1 Abs Sum |
ユーザー |
![]() |
提出日時 | 2021-02-12 21:59:58 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 813 bytes |
コンパイル時間 | 192 ms |
コンパイル使用メモリ | 82,468 KB |
実行使用メモリ | 259,352 KB |
最終ジャッジ日時 | 2024-07-19 21:20:37 |
合計ジャッジ時間 | 23,955 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 WA * 2 |
ソースコード
def f(k):b = A[k]L = sorted([abs(a - b) for a in A])return sum(L[:K]) - sum(L[K:])N, K = map(int, input().split())A = [int(a) for a in input().split()]l, r = 0, N - 1fl, fr = f(l), f(r)ans = min(fl, fr)while r - l > 2:m1 = (l * 2 + r) // 3m2 = (l + r * 2) // 3fm1, fm2 = f(m1), f(m2)if fm1 < fm2:r = m2ans = min(ans, fm1)else:l = m1ans = min(ans, fm2)if r - l > 1:ans = min(ans, f(l + r >> 1))l, r = 0, N - 1fl, fr = f(l), f(r)while r - l > 3:m1 = (l * 3 + r) // 4m2 = (l + r * 3) // 4fm1, fm2 = f(m1), f(m2)if fm1 < fm2:r = m2ans = min(ans, fm1)else:l = m1ans = min(ans, fm2)if r - l > 1:for i in range(l + 1, r):ans = min(ans, f(i))print(ans)