結果
問題 | No.1248 Kth Sum |
ユーザー | 👑 rin204 |
提出日時 | 2022-06-30 04:01:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 834 ms / 2,000 ms |
コード長 | 4,092 bytes |
コンパイル時間 | 577 ms |
コンパイル使用メモリ | 87,020 KB |
実行使用メモリ | 130,676 KB |
最終ジャッジ日時 | 2023-08-15 12:55:44 |
合計ジャッジ時間 | 12,645 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 66 ms
71,392 KB |
testcase_01 | AC | 65 ms
71,412 KB |
testcase_02 | AC | 65 ms
71,320 KB |
testcase_03 | AC | 66 ms
71,136 KB |
testcase_04 | AC | 65 ms
71,264 KB |
testcase_05 | AC | 66 ms
71,228 KB |
testcase_06 | AC | 66 ms
71,192 KB |
testcase_07 | AC | 68 ms
71,352 KB |
testcase_08 | AC | 67 ms
71,324 KB |
testcase_09 | AC | 68 ms
70,976 KB |
testcase_10 | AC | 70 ms
71,292 KB |
testcase_11 | AC | 70 ms
71,292 KB |
testcase_12 | AC | 69 ms
71,108 KB |
testcase_13 | AC | 148 ms
121,984 KB |
testcase_14 | AC | 140 ms
121,764 KB |
testcase_15 | AC | 140 ms
121,768 KB |
testcase_16 | AC | 458 ms
129,000 KB |
testcase_17 | AC | 332 ms
129,164 KB |
testcase_18 | AC | 248 ms
128,888 KB |
testcase_19 | AC | 193 ms
129,760 KB |
testcase_20 | AC | 181 ms
129,852 KB |
testcase_21 | AC | 146 ms
121,088 KB |
testcase_22 | AC | 146 ms
120,652 KB |
testcase_23 | AC | 65 ms
71,072 KB |
testcase_24 | AC | 834 ms
126,524 KB |
testcase_25 | AC | 755 ms
130,676 KB |
testcase_26 | AC | 695 ms
125,212 KB |
testcase_27 | AC | 140 ms
121,948 KB |
testcase_28 | AC | 139 ms
121,568 KB |
testcase_29 | AC | 109 ms
102,968 KB |
testcase_30 | AC | 398 ms
130,328 KB |
testcase_31 | AC | 285 ms
130,152 KB |
testcase_32 | AC | 213 ms
129,764 KB |
testcase_33 | AC | 67 ms
71,248 KB |
testcase_34 | AC | 400 ms
130,668 KB |
testcase_35 | AC | 248 ms
130,312 KB |
testcase_36 | AC | 182 ms
129,708 KB |
testcase_37 | AC | 142 ms
121,936 KB |
ソースコード
""" 部分列の個数 -> M M = 1: 自明 M = 2: 1個目 [K, 2K - 1] 2個目 [2K, N] M = 3: 1個目 [K, 3K - 2] 2個目 [2K, N] 3個目 [3K, N] M = M: 1個目 [K, M(K - 1) + 1] x個目 [xK, N] [xk, N] の部分を流用して全探索? """ class SegTree: def __init__(self, n, e, ope, lst=[]): self.N0 = 2 ** (n - 1).bit_length() self.e = e self.ope = ope self.data = [e] * (2 * self.N0) if lst: for i in range(n): self.data[self.N0 + i] = lst[i] for i in range(self.N0 - 1, 0, -1): self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1]) def build(self): for i in range(self.N0 - 1, 0, -1): self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1]) def update(self, i, x): #a_iの値をxに更新 i += self.N0 self.data[i] = x while i > 1: i >>= 1 self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1]) def add(self, i, x): self.update(i, x + self.get(i)) def set(self, i, x): self.data[self.N0 + i] = x def query(self, l, r): #区間[l, r)での演算結果 if r <= l: return self.e lres = self.e rres = self.e l += self.N0 r += self.N0 while l < r: if l & 1: lres = self.ope(lres, self.data[l]) l += 1 if r & 1: r -= 1 rres = self.ope(self.data[r], rres) l >>= 1 r >>= 1 return self.ope(lres, rres) def get(self, i): #a_iの値を返す return self.data[self.N0 + i] import heapq from heapq import * class Heapq: def __init__(self, lst = [], reverse = False): if reverse: self.pm = -1 self.hq = [-l for l in lst] else: self.pm = 1 self.hq = lst.copy() heapq.heapify(self.hq) self.tot = sum(lst) self.cnt = {} self.length = len(lst) def __bool__(self): return self.length > 0 def __len__(self): return self.length def __getitem__(self, i): if i == 0: return self.top() else: assert False def push(self, x): self.length += 1 self.cnt[x * self.pm] = self.cnt.get(x * self.pm, 0) + 1 heapq.heappush(self.hq, x * self.pm) self.tot += x def pop(self): if self.length == 0: return None self.length -= 1 ret = heapq.heappop(self.hq) self.tot -= self.pm * ret self.cnt[ret] -= 1 self.delete() return self.pm * ret def top(self): if self.hq: return self.pm * self.hq[0] else: return None def remove(self, x): if self.cnt.get(x * self.pm, 0) == 0: return False self.cnt[x * self.pm] -= 1 self.length -= 1 self.tot -= x self.delete() return True def delete(self): while self.hq and self.cnt.get(self.hq[0], 0) == 0: heapq.heappop(self.hq) n, k = map(int, input().split()) A = list(map(int, input().split())) if k == 1: print(A[0]) exit() inf = 1 << 30 def ope(x, y): if x[0] <= y[0]: return x else: return y e = (inf, -1) seg = SegTree(n, e, ope, [(a, i) for i, a in enumerate(A)]) ans = A[k - 1] ind = Heapq() hq = [] x = n // k tot = 0 for i in range(x, 1, -1): a, i = seg.query(i * k - 1, n) ind.push(i) tot += a seg.update(i, e) hq.append((-a, i)) heapify(hq) for i in range(x, 1, -1): mind = ind.top() if mind <= i * (k - 1): a = seg.query(k - 1, n)[0] ans = min(ans, tot + a) else: a = seg.query(k - 1, i * (k - 1) + 1)[0] ans = min(ans, tot + a) a, i = heappop(hq) tot += a seg.update(i, (-a, i)) ind.remove(i) print(ans)