結果
問題 | No.1391 ±1 Abs Sum |
ユーザー |
![]() |
提出日時 | 2021-02-12 23:01:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 324 ms / 2,000 ms |
コード長 | 1,173 bytes |
コンパイル時間 | 393 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 104,064 KB |
最終ジャッジ日時 | 2024-07-20 00:24:28 |
合計ジャッジ時間 | 6,276 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
mod = 1000000007 eps = 10**-9 def main(): import sys input = sys.stdin.readline N, K = map(int, input().split()) A = list(map(int, input().split())) if K == 0: ans1 = ans2 = 0 for a in A[1:]: ans1 += A[0] - a for a in A[:-1]: ans2 -= A[-1] - a print(min(ans1, ans2)) exit() cs = [0] * (N+1) for i, a in enumerate(A): cs[i+1] = cs[i] + a def calc(i, l, r): a = A[i] return cs[l] - a * l + a * (i-l) - (cs[i] - cs[l]) + (cs[N-r] - cs[i+1]) - a * (K - (i-l) - 1) + a * r - (cs[-1] - cs[N-r]) l = 0 r = N - K ans = float("inf") for _ in range(N-K+1): il = l ir = N-1-r while ir - il > 2: mid_l = (il * 2 + ir) // 3 mid_r = (il + ir * 2) // 3 val_l = calc(mid_l, l, r) val_r = calc(mid_r, l, r) if val_l < val_r: ir = mid_r else: il = mid_l ans = min(ans, calc(il, l, r), calc(ir, l, r), calc((il+ir) // 2, l, r)) l += 1 r -= 1 print(ans) if __name__ == '__main__': main()