結果

問題 No.2161 Black Market
コンテスト
ユーザー LyricalMaestro
提出日時 2024-08-14 16:05:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,942 ms / 7,000 ms
コード長 3,865 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 285 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 169,304 KB
最終ジャッジ日時 2024-08-14 16:05:50
合計ジャッジ時間 11,733 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## 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