Overview

This problem asks you to select any combination of dishes from \(N\) available dishes and maximize the “satisfaction” calculated by a specific formula. Since the number of dishes \(N\) is at most 19, which is very small, an exhaustive search examining all combinations is effective.

Analysis

The key point of this problem is estimating how many total combinations of “which dishes to select” exist.

For each dish, there are 2 choices: “select” or “don’t select.” Therefore, when there are \(N\) dishes, the total number of combinations is \(2^N\). Checking the constraints, since \(N \le 19\), the maximum number of combinations is \(2^{19} = 524{,}288\). This is sufficiently small for a computer, and calculating the satisfaction for all combinations will finish within the time limit.

The satisfaction formula is as follows: - When the total heaviness \(S_B\) is at most \(K\): satisfaction = \(S_A\) (total deliciousness) - When the total heaviness \(S_B\) exceeds \(K\): satisfaction = \(S_A - D \times (S_B - K)\)

By enumerating all combinations and applying this formula to each one to find the maximum value, we obtain the answer.

Algorithm

To efficiently compute the sums of all subsets (combinations), we use the concept of bit-based exhaustive search or dynamic programming (set expansion).

1. Enumerating all combinations: Start from the empty set (the state where nothing is ordered: total deliciousness 0, total heaviness 0).
2. Sequential addition: We incrementally add dishes — the state with the 1st dish added, the state with the 2nd dish added, and so on — expanding “for every combination built so far, add a new dish” one dish at a time.
   • When considering the \(i\)-th dish (deliciousness \(A_i\), heaviness \(B_i\)), for all combinations created so far (\(2^{i-1}\) combinations), we create new combinations by adding this dish.
3. Calculating satisfaction: For each combination, we calculate the satisfaction from the total deliciousness \(S_A\) and total heaviness \(S_B\), and keep track of the maximum value.

Complexity

• Time complexity: \(O(2^N)\) Each time a dish is added, the number of combinations doubles. When \(N=19\), the computation requires approximately \(2^{19} \approx 5.2 \times 10^5\) operations, so it runs quickly.
• Space complexity: \(O(2^N)\) If we store the total values of all combinations in a list, we need memory to hold \(2^N\) elements. For \(N=19\), this is only a few MB, so there is no issue.

Implementation Details

In the provided code, the following optimizations are used to achieve fast execution in Python: - List comprehensions and slicing: By writing expressions like sums_A[bit : 2*bit] = [x + a for x in sums_A[:bit]], Python’s internally optimized loops run, computing the sums of all combinations faster than appending individually with append. - Batch computation: Instead of the \(O(N \cdot 2^N)\) approach of looping through each bitmask (from \(0\) to \(2^N-1\)) and checking “which bits are set,” the method described above reuses previous results to compute in \(O(2^N)\). This significantly reduces execution time.

Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 料理の数 N、上限 K、減少量 D を取得します
    N = int(input_data[0])
    K = int(input_data[1])
    D = int(input_data[2])
    
    # 各料理のおいしさ A とこってり度 B を格納するリストを作成します
    dishes_A = []
    dishes_B = []
    for i in range(N):
        dishes_A.append(int(input_data[3 + 2*i]))
        dishes_B.append(int(input_data[4 + 2*i]))
        
    # すべての料理の組み合わせ（2^N 通り）について、おいしさの合計とこってり度の合計を計算します
    # sums_A[i] は i 番目のビットマスクに対応する料理の組み合わせのおいしさの合計を保持します
    num_combinations = 1 << N
    sums_A = [0] * num_combinations
    sums_B = [0] * num_combinations
    
    # 動的計画法（集合の拡張）を用いて、すべての部分集合の和を効率的に計算します
    for i in range(N):
        a = dishes_A[i]
        b = dishes_B[i]
        bit = 1 << i
        # すでに計算された部分集合に現在の料理を加えた新しい部分集合を作成します
        # スライスとリスト内包表記を使用することで、Pythonでの実行速度を向上させます
        sums_A[bit : 2*bit] = [x + a for x in sums_A[:bit]]
        sums_B[bit : 2*bit] = [x + b for x in sums_B[:bit]]
        
    # 得られる満足度の最大値を求めます
    # 初期値は「1品も注文しない」場合の満足度である 0 です
    max_sat = 0
    for sa, sb in zip(sums_A, sums_B):
        # 満足度の計算式: (おいしさの合計) - D * max(0, こってり度の合計 - K)
        if sb > K:
            current_sat = sa - D * (sb - K)
        else:
            current_sat = sa
        
        # 最大値を更新します
        if current_sat > max_sat:
            max_sat = current_sat
            
    # 結果を出力します
    print(max_sat)

if __name__ == '__main__':
    solve()

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