Overview

This is a problem of maximizing the total price of given items within a budget of \(K\) yen. This is a classic dynamic programming (DP) problem known as the “subset sum problem,” which requires efficiently searching for the optimal combination within the budget.

Analysis

1. Straightforward Approach (Brute Force)

Since each item has 2 choices — “buy” or “don’t buy” — there are a total of \(2^N\) possible combinations. In this problem, \(N \leq 100\), so the number of combinations is \(2^{100} \approx 1.26 \times 10^{30}\), making it impossible to examine all of them within the time limit.

2. Solution Using Dynamic Programming (DP)

We consider adding items one by one while maintaining information about “whether it is possible to achieve a certain amount \(j\).” We prepare an array where \(dp[j]\) is “true if a total amount of \(j\) can be achieved, false otherwise.” Each time we add a new item with price \(C_i\), for every amount \(j\) that can already be achieved, \(j + C_i\) also becomes achievable. By performing this update for amounts up to the budget \(K\), the computational complexity can be kept to \(O(NK)\).

3. Speedup Using Bitset

This DP can be further sped up using “bit operations.” We treat a large integer as a single “sequence of bits,” where if the \(j\)-th bit is 1, it means “amount \(j\) can be achieved.” The operation of adding a new price \(c\) corresponds to left-shifting the current bit sequence by \(c\) (<< c) and taking the logical OR (OR) with the original bit sequence. Since Python supports arbitrary-precision integers, this bit operation can be performed very concisely and efficiently.

Algorithm

1. Initialization:
   • Since a total of 0 yen can always be achieved, set reachable = 1 (in binary: ...0001).
   • Prepare a mask where the lowest \(K+1\) bits are all 1, to ignore amounts exceeding the budget \(K\).
2. Update:
   • For each item’s price \(c\), repeat the following:
   • reachable |= (reachable << c)
   • Apply the mask to clear bits exceeding the budget \(K\).
3. Extracting the Answer:
   • The position (index) of the highest set bit in reachable is the maximum total amount within the budget \(K\).
   • Using Python’s bit_length() method, you can easily obtain “which position the highest bit is at.”

Complexity

• Time Complexity: \(O(NK / w)\)
  • \(N\) is the number of items and \(K\) is the budget. \(w\) corresponds to the CPU’s word size (optimization through Python’s internal implementation). By using bit operations, this runs tens of times faster than DP with ordinary loops.
• Space Complexity: \(O(K)\)
  • Memory is needed to hold a single bit sequence (a huge integer) representing states up to the budget \(K\).

Implementation Notes

• Utilizing Bit Operations: The single line reachable |= (reachable << c) collectively computes the transition of “adding a new item” for all amounts that could be achieved so far.

• Budget Restriction: By performing reachable &= mask each time an item is added, unnecessary information exceeding the budget \(K\) is trimmed, preventing the number from growing excessively large.

• Obtaining the Result: bit_length() - 1 returns the position of the leftmost 1 when the integer is represented in binary. For example, if reachable is 1010 in binary (10 in decimal), then bit_length() is 4, meaning the maximum achievable amount is \(4 - 1 = 3\).

  Source Code

import sys

def solve():
    # 入力を取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    c_list = list(map(int, input_data[2:]))
    
    # ビットセットを用いた動的計画法 (DP)
    # reachable の i 番目のビットが 1 ならば、合計金額 i が可能であることを示す
    reachable = 1
    
    # 予算 K を超えるビットを無視するためのマスク
    mask = (1 << (k + 1)) - 1
    
    for c in c_list:
        # 新しい商品 c を加える場合、現在の可能金額を c だけシフトして OR を取る
        reachable |= (reachable << c)
        # 予算 K を超える部分は不要なのでマスクする
        reachable &= mask
    
    # reachable の最も上位のビット（bit_length - 1）が K 以下の最大合計金額となる
    print(reachable.bit_length() - 1)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.