結果
問題 |
No.2304 Distinct Elements
|
ユーザー |
|
提出日時 | 2024-03-16 15:41:06 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,340 bytes |
コンパイル時間 | 226 ms |
コンパイル使用メモリ | 82,376 KB |
実行使用メモリ | 118,812 KB |
最終ジャッジ日時 | 2024-09-30 04:03:04 |
合計ジャッジ時間 | 13,780 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 WA * 26 |
ソースコード
from heapq import * class SlopeTrick: def __init__(self): self.minf = 0 self.inf = 1 << 60 self.R = [self.inf] self.L = [self.inf] self.addr = 0 self.addl = 0 @property def min(self): return self.minf def get_min(self): return (self.minf, -self.L[0] + self.addl, self.R[0] + self.addr) # add f(x) = a def add(self, a): self.minf += a # add f(x) = max(0, x - a) def add_x_a(self, a): self.minf += max(0, -self.L[0] + self.addl - a) heappush(self.L, self.addl - a) heappush(self.R, -heappop(self.L) + self.addl - self.addr) # add f(x) = max(0, a - x) def add_a_x(self, a): self.minf += max(0, a - self.R[0] - self.addr) heappush(self.R, a - self.addr) heappush(self.L, -heappop(self.R) - self.addr + self.addl) # add f(x) = abs(x - a) def add_abs(self, a): self.add_a_x(a) self.add_x_a(a) def add_l(self, x): assert x <= 0 self.addl += x def add_r(self, x): assert x >= 0 self.addr += x n = int(input()) A = list(map(int, input().split())) A.sort() for i in range(n): A[i] -= i st = SlopeTrick() for a in A: st.add_abs(a) while len(st.R) > 1: st.add_a_x(-heappop(st.R)) print(st.min)