結果
問題 | No.1391 ±1 Abs Sum |
ユーザー |
![]() |
提出日時 | 2021-02-12 22:07:29 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 977 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 265,128 KB |
最終ジャッジ日時 | 2024-07-19 21:55:30 |
合計ジャッジ時間 | 24,549 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 TLE * 3 -- * 13 |
ソースコード
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()]# 1l, 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))# 2mi = 10 ** 60mii = -1s = max(1, N // 300)for i in range(0, N, s):fi = f(i)if fi < mi:mi = fimii = ians = min(ans, mi)l = max(0, mii - s)r = min(N, mii + s)while r - l > 3: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:for i in range(l + 1, r):ans = min(ans, f(i))print(ans)