結果

問題 No.2161 Black Market
ユーザー lam6er
提出日時 2025-03-20 20:35:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,554 ms / 7,000 ms
コード長 3,465 bytes
コンパイル時間 453 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 160,880 KB
最終ジャッジ日時 2025-03-20 20:36:53
合計ジャッジ時間 20,477 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from collections import defaultdict

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [[] for _ in range(2 * self.size)]
        for i in range(self.n):
            self.tree[self.size + i] = [data[i]]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.merge(self.tree[2 * i], self.tree[2 * i + 1])

    def merge(self, left, right):
        merged = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged

    def query_ge(self, l, r, x):
        res = 0
        l += self.size
        r += self.size + 1
        while l < r:
            if l % 2 == 1:
                res += len(self.tree[l]) - bisect.bisect_left(self.tree[l], x)
                l += 1
            if r % 2 == 1:
                r -= 1
                res += len(self.tree[r]) - bisect.bisect_left(self.tree[r], x)
            l //= 2
            r //= 2
        return res

def generate_subsets(cards):
    n = len(cards)
    subsets = []
    for mask in range(1 << n):
        sum_a = sum_b = count = 0
        for i in range(n):
            if mask & (1 << i):
                sum_a += cards[i][0]
                sum_b += cards[i][1]
                count += 1
        subsets.append((sum_a, sum_b, count))
    return subsets

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr]); ptr += 1
    K = int(input[ptr]); ptr += 1
    L = int(input[ptr]); ptr += 1
    P = int(input[ptr]); ptr += 1
    cards = []
    for _ in range(N):
        a = int(input[ptr]); ptr += 1
        b = int(input[ptr]); ptr += 1
        cards.append((a, b))
    
    mid = N // 2
    first_half = cards[:mid]
    second_half = cards[mid:]
    
    first_subsets = generate_subsets(first_half)
    second_subsets = generate_subsets(second_half)
    
    groups_second = defaultdict(list)
    for a, b, c in second_subsets:
        if c <= K:
            groups_second[c].append((a, b))
    
    group_info = {}
    for count in groups_second:
        subsets = groups_second[count]
        sorted_subsets = sorted(subsets, key=lambda x: x[0])
        a_list = [x[0] for x in sorted_subsets]
        b_list = [x[1] for x in sorted_subsets]
        if not b_list:
            group_info[count] = (a_list, None)
            continue
        st = SegmentTree(b_list)
        group_info[count] = (a_list, st)
    
    total = 0
    for a1, b1, c1 in first_subsets:
        if c1 > K:
            continue
        max_c2 = K - c1
        sumA1 = a1
        sumB1 = b1
        maxA_total = L - sumA1
        if maxA_total < 0:
            continue
        for c2 in range(0, max_c2 + 1):
            if c2 not in group_info:
                continue
            a_list, st = group_info[c2]
            if st is None:
                continue
            idx = bisect.bisect_right(a_list, maxA_total) - 1
            if idx < 0:
                continue
            sumB_need = max(0, P - sumB1)
            cnt = st.query_ge(0, idx, sumB_need)
            total += cnt
    print(total)

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