結果
問題 | No.738 平らな農地 |
ユーザー |
|
提出日時 | 2022-03-11 18:12:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 342 ms / 2,000 ms |
コード長 | 1,616 bytes |
コンパイル時間 | 169 ms |
コンパイル使用メモリ | 82,036 KB |
実行使用メモリ | 123,904 KB |
最終ジャッジ日時 | 2024-09-15 21:35:25 |
合計ジャッジ時間 | 19,799 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 87 |
ソースコード
#BIT plus verclass BITplus:def __init__(self,N):self.N = Nself.bit = [0] * (self.N+1)def add(self,i,x):while i <= self.N:self.bit[i] += xi += i & -idef fold(self,i):ans = 0while i > 0:ans += self.bit[i]i -= i & -ireturn ansdef lb(self,w):if w <= 0:return 0x = 0k = 1while k <= self.N:k <<= 1k >>= 1while k:if x + k <= self.N and self.bit[x+k] < w:w -= self.bit[x+k]x += kk >>= 1return x + 1#サイズ N の配列をいれるdef build(self,seq):bit = self.bitN = self.Nfor i in range(N):bit[i+1] = seq[i]for i in range(1,N+1):if i + (i & -1) <= N:bit[i + (i & -i)] += bit[i]N,K = map(int,input().split())A = list(map(int,input().split()))rD = sorted(set(A))D = {v:i for i,v in enumerate(rD)}n = len(D)bit1 = BITplus(n)bit2 = BITplus(n)mid = (K+1) // 2for i in range(K):a = A[i]bit1.add(D[a]+1,1)bit2.add(D[a]+1,a)ans = 10 ** 18for i in range(K-1,N):if i >= K:a = A[i]b = A[i-K]bit1.add(D[a]+1,1)bit2.add(D[a]+1,a)bit1.add(D[b]+1,-1)bit2.add(D[b]+1,-b)m = bit1.lb(mid)mm = bit1.fold(m)t1 = bit2.fold(m)t2 = bit2.fold(n) - t1tmp = rD[m-1] * mm - t1 + t2 - rD[m-1] * (K - mm)if tmp < ans:ans = tmp#print(m,mm,t1,t2,tmp)print(ans)