結果
問題 | No.2161 Black Market |
ユーザー | 👑 Kazun |
提出日時 | 2022-12-12 18:35:36 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 8,507 bytes |
コンパイル時間 | 317 ms |
コンパイル使用メモリ | 82,528 KB |
実行使用メモリ | 257,660 KB |
最終ジャッジ日時 | 2024-11-06 17:13:01 |
合計ジャッジ時間 | 11,159 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 45 ms
56,576 KB |
testcase_01 | AC | 46 ms
57,540 KB |
testcase_02 | AC | 94 ms
76,796 KB |
testcase_03 | AC | 46 ms
56,224 KB |
testcase_04 | AC | 46 ms
55,816 KB |
testcase_05 | AC | 45 ms
56,452 KB |
testcase_06 | AC | 87 ms
76,932 KB |
testcase_07 | RE | - |
testcase_08 | AC | 118 ms
78,092 KB |
testcase_09 | AC | 105 ms
77,196 KB |
testcase_10 | AC | 113 ms
77,952 KB |
testcase_11 | RE | - |
testcase_12 | AC | 89 ms
77,480 KB |
testcase_13 | AC | 59 ms
65,536 KB |
testcase_14 | AC | 66 ms
68,224 KB |
testcase_15 | AC | 109 ms
77,952 KB |
testcase_16 | RE | - |
testcase_17 | AC | 46 ms
55,552 KB |
testcase_18 | AC | 47 ms
55,296 KB |
testcase_19 | AC | 58 ms
64,512 KB |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | AC | 505 ms
79,328 KB |
testcase_23 | AC | 1,114 ms
81,152 KB |
testcase_24 | AC | 1,692 ms
253,884 KB |
testcase_25 | RE | - |
testcase_26 | AC | 1,455 ms
257,660 KB |
testcase_27 | AC | 211 ms
89,600 KB |
testcase_28 | AC | 253 ms
101,224 KB |
testcase_29 | RE | - |
testcase_30 | RE | - |
testcase_31 | AC | 1,005 ms
236,004 KB |
testcase_32 | AC | 142 ms
76,672 KB |
testcase_33 | RE | - |
testcase_34 | AC | 81 ms
76,416 KB |
testcase_35 | AC | 86 ms
76,160 KB |
testcase_36 | AC | 78 ms
75,776 KB |
testcase_37 | RE | - |
testcase_38 | AC | 94 ms
75,776 KB |
testcase_39 | RE | - |
ソースコード
class Binary_Trie: """ Reference https://judge.yosupo.jp/submission/35057 https://judge.yosupo.jp/submission/53782 """ def __init__(self, max_value, allow_multiple=False, query_number=None): self.bit=max_value.bit_length() self.upper=1<<self.bit self.multi=allow_multiple if query_number!=None: self.arc=[-1]*2*self.bit*(query_number+1) self.size=[0]*self.bit*(query_number+1) self.terminal=[0]*self.bit*(query_number+1) self.id=0 else: self.arc=[-1,-1] self.size=[0] self.terminal=[0] self.query_number=query_number self.v_list=[0]*(self.bit+1) self.lazy_xor=0 def xor_all(self, x): assert 0<=x<self.upper self.lazy_xor^=x def __ixor__(self, x): self.xor_all(x) return self def insert(self, x): """ x を追加する. """ assert 0<=x<self.upper x^=self.lazy_xor v=0 for i in reversed(range(self.bit)): d=(x>>i)&1 if self.arc[2*v+d]==-1: if self.query_number!=None: self.id+=1 self.arc[2*v+d]=self.id else: self.arc[2*v+d]=len(self.size) self.arc.append(-1); self.arc.append(-1) self.terminal.append(0) self.size.append(0) v=self.arc[2*v+d] self.v_list[i]=v if self.multi or self.terminal[v]==0: self.terminal[v]+=1 for w in self.v_list: self.size[w]+=1 def discard(self, x): """ x が存在する場合, x を削除する. """ if not (0<=x<self.upper): return x^=self.lazy_xor v=0 for i in reversed(range(self.bit)): d=(x>>i)&1 if self.arc[2*v+d]==-1: return v=self.arc[2*v+d] self.v_list[i]=v if self.terminal[v]>0: self.terminal[v]-=1 for w in self.v_list: self.size[w]-=1 def erase(self, x, k): """ x を高々 k 回削除する (ただし, k=-1 のときは無限回)""" assert -1<=k if not (0<=x<self.upper): return x^=self.lazy_xor v=0 for i in reversed(range(self.bit)): d=(x>>i)&1 if self.arc[2*v+d]==-1: return v=self.arc[2*v+d] self.v_list[i]=v if (k==-1) or (self.terminal[v]<k): k=self.terminal[v] if self.terminal[v]>0: self.terminal[v]-=k for w in self.v_list: self.size[w]-=k def count(self, x): """ x の個数を求める. """ if not (0<=x<self.upper): return 0 x^=self.lazy_xor v=0 for i in reversed(range(self.bit)): d=(x>>i)&1 if self.arc[2*v+d]==-1: return 0 v=self.arc[2*v+d] return self.terminal[v] def __contains__(self, x): return bool(self.count(x)) def __len__(self): return self.size[0] def __bool__(self): return bool(len(self)) def less_count(self, x, equal=False): """ x 未満の要素数を求める (equal=True のときは, "未満" が "以下" になる)""" x^=self.lazy_xor if equal: x+=1 if x<0: return 0 if self.upper<=x: return len(self) v=0 res=0 for i in reversed(range(self.bit)): d=(x>>i)&1 lc=self.arc[2*v] rc=self.arc[2*v+1] if (self.lazy_xor>>i)&1: lc,rc=rc,lc if d: if lc!=-1: res+=self.size[lc] if rc==-1: return res v=rc else: if lc==-1: return res v=lc return res def more_count(self, x, equal=False): """ x より大きい要素数を求める (equal=True のときは, "より大きい" が "以上" になる)""" return len(self)-self.less_count(x,not equal) def low_value(self, x, equal=False, default=None): """ x 未満の整数のうち, 最大の整数を求める (存在しない場合は default). equal: True のとき, "未満" が "以下" になる. """ x^=self.lazy_xor if equal: x+=1 alpha=self.less_count(x,False) if alpha==0: return default else: return self.kth_element(alpha,1) def high_value(self, x, equal=False, default=None): """ x より大きい整数のうち, 最小の整数を求める (存在しない場合は default) equal: True のとき, "より大きい" が "以上" になる. """ x^=self.lazy_xor if equal: x-=1 beta=self.more_count(x,False) if beta==0: return default else: return self.kth_element(-beta,0) def kth_element(self, k, index=0, default=-1): """ index -indexed で k 番目に小さい値を求める. ただし, index=0, k<0 のときは |k| 番目に大きい値になる. """ if k<0: k+=self.size[0] k-=index if not (0<=k<self.size[0]): return default v=0 res=0 for i in reversed(range(self.bit)): lc=self.arc[2*v] rc=self.arc[2*v+1] if (self.lazy_xor>>i)&1: lc,rc=rc,lc if lc==-1: v=rc res|=1<<i elif self.size[lc]<=k: k-=self.size[lc] v=rc res|=1<<i else: v=lc return res def get_min(self): return self.kth_element(1,1) def get_max(self): return self.kth_element(-1) def get_median(self, mode=0, func=None): """ 中央値を求める. [mode] 項の数が偶数のときの中央値の求め方を指定する (その 2値を a,b (a<=b) とする). mode=-1 → a mode= 0 → (a+b)/2 (float 型) mode= 1 → b mode=(その他) → その他 ( 2変数関数 func(a,b) で指定) """ if len(self)%2==1: return self.kth_element(len(self)//2) else: a=self.kth_element(len(self)//2) b=self.kth_element(len(self)//2-1) if mode==-1: return a elif mode==1: return b elif mode==0: return (a+b)/2 else: return func(a,b) def __getitem__(self, index): return self.kth_element(index) #================================================== def solve(): from operator import itemgetter from collections import defaultdict N,K,L,P=map(int,input().split()) A=[0]*N; B=[0]*N for i in range(N): A[i],B[i]=map(int,input().split()) def bit(x,k): return (x>>k)&1 def calc(C,D): T=[defaultdict(list) for _ in range(K+1)] N=len(C) for S in range(1<<N): cost=0; value=0; count=0 for i in range(N): if bit(S,i): cost+=C[i] count+=1 value+=D[i] if cost<=L and count<=K: T[count][cost].append(value) return [sorted(T[k]) for k in range(K+1)], T F0,G0=calc(A[:N//2], B[:N//2]) F1,G1=calc(A[N//2:], B[N//2:]) T=[Binary_Trie(10**9, True) for _ in range(K+1)] for k in range(K+1): t=T[k] for c in F1[k]: for w in G1[k][c]: t.insert(w) F=[] for k in range(K+1): F.extend([(cost,k) for cost in F0[k]]) F.sort(key=itemgetter(0)) X=0 for cost,k in F: for r in range(K+1): while F1[r] and cost+F1[r][-1]>L: for w in G1[r][F1[r][-1]]: T[r].discard(w) F1[r].pop() if k+r<=K: for value in G0[k][cost]: X+=T[r].more_count(max(0, P-value), True) return X #================================================== print(solve())