結果
問題 | No.2232 Miser's Gift |
ユーザー | タコイモ |
提出日時 | 2023-03-03 21:34:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,122 ms / 2,000 ms |
コード長 | 3,390 bytes |
コンパイル時間 | 1,136 ms |
コンパイル使用メモリ | 81,560 KB |
実行使用メモリ | 87,568 KB |
最終ジャッジ日時 | 2023-10-18 01:31:00 |
合計ジャッジ時間 | 34,981 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
55,296 KB |
testcase_01 | AC | 44 ms
55,296 KB |
testcase_02 | AC | 44 ms
55,296 KB |
testcase_03 | AC | 842 ms
87,112 KB |
testcase_04 | AC | 866 ms
85,024 KB |
testcase_05 | AC | 172 ms
77,536 KB |
testcase_06 | AC | 45 ms
55,296 KB |
testcase_07 | AC | 831 ms
85,160 KB |
testcase_08 | AC | 882 ms
84,652 KB |
testcase_09 | AC | 889 ms
84,556 KB |
testcase_10 | AC | 899 ms
84,704 KB |
testcase_11 | AC | 898 ms
84,588 KB |
testcase_12 | AC | 896 ms
84,620 KB |
testcase_13 | AC | 909 ms
87,568 KB |
testcase_14 | AC | 908 ms
87,212 KB |
testcase_15 | AC | 902 ms
87,224 KB |
testcase_16 | AC | 885 ms
87,272 KB |
testcase_17 | AC | 833 ms
87,084 KB |
testcase_18 | AC | 837 ms
87,228 KB |
testcase_19 | AC | 833 ms
87,080 KB |
testcase_20 | AC | 833 ms
87,136 KB |
testcase_21 | AC | 856 ms
87,432 KB |
testcase_22 | AC | 834 ms
87,344 KB |
testcase_23 | AC | 996 ms
85,124 KB |
testcase_24 | AC | 1,024 ms
85,340 KB |
testcase_25 | AC | 999 ms
85,256 KB |
testcase_26 | AC | 1,065 ms
85,256 KB |
testcase_27 | AC | 1,122 ms
85,364 KB |
testcase_28 | AC | 997 ms
85,208 KB |
testcase_29 | AC | 985 ms
85,196 KB |
testcase_30 | AC | 994 ms
85,004 KB |
testcase_31 | AC | 973 ms
85,464 KB |
testcase_32 | AC | 994 ms
85,240 KB |
testcase_33 | AC | 899 ms
86,780 KB |
testcase_34 | AC | 906 ms
86,524 KB |
testcase_35 | AC | 909 ms
86,580 KB |
testcase_36 | AC | 902 ms
86,672 KB |
testcase_37 | AC | 911 ms
86,596 KB |
testcase_38 | AC | 89 ms
75,620 KB |
testcase_39 | AC | 89 ms
75,628 KB |
testcase_40 | AC | 90 ms
75,620 KB |
testcase_41 | AC | 91 ms
75,632 KB |
testcase_42 | AC | 90 ms
75,624 KB |
testcase_43 | AC | 90 ms
75,624 KB |
testcase_44 | AC | 92 ms
75,716 KB |
testcase_45 | AC | 91 ms
75,624 KB |
testcase_46 | AC | 90 ms
75,608 KB |
testcase_47 | AC | 89 ms
75,716 KB |
testcase_48 | AC | 68 ms
72,184 KB |
testcase_49 | AC | 69 ms
72,176 KB |
testcase_50 | AC | 69 ms
72,192 KB |
testcase_51 | AC | 68 ms
72,180 KB |
testcase_52 | AC | 69 ms
72,184 KB |
testcase_53 | AC | 70 ms
72,192 KB |
testcase_54 | AC | 68 ms
72,176 KB |
testcase_55 | AC | 70 ms
72,180 KB |
testcase_56 | AC | 70 ms
72,184 KB |
testcase_57 | AC | 71 ms
72,192 KB |
ソースコード
from collections import defaultdict #####segfunc##### def segfunc(x, y): return max(x,y) ################# #####ide_ele##### ide_ele = 0 ################# class SegTree: """ init(init_val, ide_ele): 配列init_valで初期化 O(N) update(k, x): k番目の値をxに更新 O(logN) query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN) """ def __init__(self, init_val, segfunc, ide_ele): """ init_val: 配列の初期値 segfunc: 区間にしたい操作 ide_ele: 単位元 n: 要素数 num: n以上の最小の2のべき乗 tree: セグメント木(1-index) """ n = len(init_val) self.segfunc = segfunc self.ide_ele = ide_ele self.num = 1 << (n - 1).bit_length() self.tree = [ide_ele] * 2 * self.num # 配列の値を葉にセット for i in range(n): self.tree[self.num + i] = init_val[i] # 構築していく for i in range(self.num - 1, 0, -1): self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1]) def update(self, k, x): """ k番目の値をxに更新 k: index(0-index) x: update value """ k += self.num self.tree[k] = x while k > 1: self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1]) k >>= 1 def query(self, l, r): """ [l, r)のsegfuncしたものを得る l: index(0-index) r: index(0-index) """ res = self.ide_ele l += self.num r += self.num while l < r: if l & 1: res = self.segfunc(res, self.tree[l]) l += 1 if r & 1: res = self.segfunc(res, self.tree[r - 1]) l >>= 1 r >>= 1 return res import sys #sys.setrecursionlimit(500000) def I(): return int(sys.stdin.readline().rstrip()) def MI(): return map(int,sys.stdin.readline().rstrip().split()) def TI(): return tuple(map(int,sys.stdin.readline().rstrip().split())) def LI(): return list(map(int,sys.stdin.readline().rstrip().split())) def S(): return sys.stdin.readline().rstrip() def LS(): return list(sys.stdin.readline().rstrip()) #for i, pi in enumerate(p): from collections import defaultdict,deque import bisect import itertools dic = defaultdict(int) d = deque() YN = ['No','Yes'] N,W = MI() dp = [-1]*(W+1) #for _ in range(N)] dp[0] = 0 for _ in range(N): w,v = MI() for i in range(W-w,-1,-1): if dp[i] == -1: continue dp[i+w] = max(dp[i]+v,dp[i+w]) mdp = max(dp) seg = SegTree(dp, segfunc, ide_ele) #https://aotamasaki.hatenablog.com/entry/meguru_bisect def is_ok(arg,x): return mdp < seg.query(0,W-x+1)+arg # return #満たすべき条件a<b等 #ngは必ず答えにならない値 def meguru_bisect(ng, ok,x): ''' 初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す まずis_okを定義すべし ng ok は とり得る最小の値-1 とり得る最大の値+1 最大最小が逆の場合はよしなにひっくり返す ''' while (abs(ok - ng) > 1): mid = (ok + ng) // 2 if is_ok(mid,x): ok = mid else: ng = mid return ok for x in range(1,W+1): print(meguru_bisect(0, 10**10,x))