結果

問題 No.2161 Black Market
ユーザー LyricalMaestroLyricalMaestro
提出日時 2024-08-14 16:05:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,942 ms / 7,000 ms
コード長 3,865 bytes
コンパイル時間 285 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 169,304 KB
最終ジャッジ日時 2024-08-14 16:05:50
合計ジャッジ時間 11,733 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
52,480 KB
testcase_01 AC 39 ms
52,608 KB
testcase_02 AC 59 ms
67,712 KB
testcase_03 AC 37 ms
52,608 KB
testcase_04 AC 37 ms
52,096 KB
testcase_05 AC 36 ms
52,480 KB
testcase_06 AC 67 ms
73,728 KB
testcase_07 AC 65 ms
72,064 KB
testcase_08 AC 66 ms
71,424 KB
testcase_09 AC 61 ms
68,992 KB
testcase_10 AC 77 ms
71,680 KB
testcase_11 AC 62 ms
70,272 KB
testcase_12 AC 58 ms
66,816 KB
testcase_13 AC 39 ms
52,480 KB
testcase_14 AC 38 ms
53,248 KB
testcase_15 AC 61 ms
70,496 KB
testcase_16 AC 52 ms
64,128 KB
testcase_17 AC 38 ms
52,480 KB
testcase_18 AC 36 ms
52,480 KB
testcase_19 AC 52 ms
64,128 KB
testcase_20 AC 614 ms
98,792 KB
testcase_21 AC 578 ms
99,168 KB
testcase_22 AC 296 ms
92,928 KB
testcase_23 AC 697 ms
99,908 KB
testcase_24 AC 1,942 ms
169,304 KB
testcase_25 AC 734 ms
130,560 KB
testcase_26 AC 1,761 ms
161,756 KB
testcase_27 AC 159 ms
76,936 KB
testcase_28 AC 168 ms
81,920 KB
testcase_29 AC 130 ms
82,304 KB
testcase_30 AC 110 ms
79,104 KB
testcase_31 AC 886 ms
159,872 KB
testcase_32 AC 118 ms
75,648 KB
testcase_33 AC 154 ms
83,712 KB
testcase_34 AC 71 ms
75,520 KB
testcase_35 AC 73 ms
76,160 KB
testcase_36 AC 63 ms
75,520 KB
testcase_37 AC 65 ms
73,600 KB
testcase_38 AC 90 ms
75,720 KB
testcase_39 AC 57 ms
72,576 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2161

class BinaryIndexTree:
    """
    フェニック木(BinaryIndexTree)の基本的な機能を実装したクラス
    """
    def __init__(self, size):
        self.size = size
        self.array = [0] * (size + 1)
    
    def add(self, x, a):
        index = x
        while index <= self.size:
            self.array[index] += a
            index += index & (-index)
    
    def sum(self, x):
        index = x
        ans = 0
        while index > 0:
            ans += self.array[index]
            index -= index & (-index)
        return ans

    def least_upper_bound(self, value):
        if self.sum(self.size) < value:
            return -1
        elif value <= 0:
            return 0

        m = 1
        while m < self.size:
            m *= 2

        k = 0
        k_sum = 0
        while m > 0:
            k0 = k + m
            if k0 < self.size:
                if k_sum + self.array[k0] < value:
                    k_sum += self.array[k0]
                    k += m
            m //= 2
        if k < self.size:
            return k + 1
        else:
            return -1


def main():
    N, K, L, P = map(int, input().split())
    ab = []
    for _ in range(N):
        a, b = map(int, input().split())
        ab.append((a, b))

    if N == 1:
        if a <= L and b >= P:
            print(1)
        else:
            print(0)
        return
    
    n1 = N // 2
    cost_value_array = []
    k_map = {}
    for bit in range(2 ** n1):
        total_cost = 0
        total_value = 0
        k = 0
        for i in range(n1):
            if bit & (1 << i) > 0:
                k += 1
                a, b = ab[i]
                total_cost += a
                total_value += b
        
        if k <= K and total_cost <= L:
            if k not in k_map:
                k_map[k] = []
            k_map[k].append((total_cost, total_value))        
    
    n2 = N - n1
    k2_map = {}
    for bit in range(2 ** n2):
        total_cost = 0
        total_value = 0
        k = 0
        for i in range(n2):
            if bit & (1 << i) > 0:
                k += 1
                a, b = ab[i + n1]
                total_cost += a
                total_value += b
        
        if k <= K and total_cost <= L:
            if k not in k2_map:
                k2_map[k] = []
            k2_map[k].append((total_cost, total_value))

    # valueたちについての座標圧縮
    value_set = set()
    for values in k_map.values():
        for _, v in values:
            value_set.add(v)
    for values in k2_map.values():
        for _, v in values:
            value_set.add(P - v)
    value_list = list(value_set)
    value_list.sort()
    value_map = {}
    for i, v in enumerate(value_list):
        value_map[v] = i + 1
    v_max = len(value_list)

        
    # n2側に使える最大の個数についてforを回す
    n1_array = []
    next_k1 = 0    
    answer = 0
    for k2 in reversed(range(K + 1)):
        if k2 not in k2_map:
            continue

        bit = BinaryIndexTree(v_max)
        target_array = k2_map[k2]
        target_array.sort(key=lambda x : x[0], reverse=True)

        while next_k1 + k2 <= K:
            if next_k1 in k_map:
                for cost, value in k_map[next_k1]:
                    n1_array.append((cost, value))

            next_k1 += 1
        n1_array.sort(key=lambda x : x[0])

        ind = 0
        for n2_cost, n2_value in target_array:
            while ind < len(n1_array) and n1_array[ind][0] <= L - n2_cost:
                value = n1_array[ind][1]
                bit.add(value_map[value], 1)
                ind += 1

            t_value = value_map[P - n2_value]
            ans = bit.sum(bit.size) - bit.sum(t_value - 1)
            answer += ans
    print(answer)












if __name__ == "__main__":
    main()
0