Overview

From \(N\) dishes, we select any combination to maximize the “satisfaction,” defined as the total deliciousness minus the penalty for exceeding the richness limit. Given the constraint \(N \leq 19\), we enumerate all combinations (bit brute-force) to solve the problem.

Analysis

Problem Formulation

Let \(S\) be the set of chosen dishes. The satisfaction is determined by the following formula:

\[\text{Satisfaction} = \sum_{i \in S} A_i - D \times \max\!\left(0,\ \sum_{i \in S} B_i - K\right)\]

We want to choose dishes with a large total deliciousness, but if the total richness exceeds \(K\), a penalty proportional to \(D\) is applied. Therefore, simply “choosing all delicious dishes” is not necessarily optimal.

Why Greedy Approaches Don’t Work

• Sorting and selecting by deliciousness alone overlooks the richness penalty.
• Even if we sort by “cost-effectiveness” considering richness, the penalty only applies to the amount exceeding \(K\). The situation changes at this threshold, so a greedy approach cannot produce the correct answer.

The Hint: \(N \leq 19\)

Since \(N\) is at most \(19\), the total number of ways to select dishes is only \(2^{19} = 524{,}288\). This makes it feasible to exhaustively check all combinations.

Algorithm

We use bit brute-force (bitmask enumeration).

1. Iterate through integers \(\text{mask}\) from \(0\) to \(2^N - 1\).
2. If the \(i\)-th bit of \(\text{mask}\) is \(1\), interpret it as “order the \(i\)-th dish.”
3. For each \(\text{mask}\), compute the total deliciousness \(sa\) and the total richness \(sb\) of the selected dishes.
4. Calculate the satisfaction \(sa - D \times \max(0, sb - K)\) and update the maximum value.
5. The satisfaction when nothing is ordered (\(\text{mask} = 0\)) is \(0\), so initialize the answer to \(0\).

Example: When \(N = 3\), \(\text{mask} = 5 = (101)_2\) means “order dish \(0\) and dish \(2\).”

mask (binary)	Selected dishes
000	None
001	Dish 0
010	Dish 1
011	Dish 0, 1
100	Dish 2
101	Dish 0, 2
110	Dish 1, 2
111	Dish 0, 1, 2

Complexity

• Time Complexity: \(O(N \cdot 2^N)\)
  • For each of the \(2^N\) subsets, we scan \(N\) bits to compute the totals.
  • When \(N = 19\), this is approximately \(19 \times 524{,}288 \approx 10^7\) operations, which is sufficiently fast.
• Space Complexity: \(O(N)\)
  • Only the arrays holding the dish information are needed.

Implementation Notes

• Initialize to \(0\): Since the satisfaction of ordering nothing is \(0\), initialize with best = 0. This ensures the correct output of \(0\) even when all combinations yield negative satisfaction.

• Bit operation mask & (1 << i): This checks whether the \(i\)-th bit of \(\text{mask}\) is set. This allows us to efficiently manage whether each dish is selected or not.

• Fast input with sys.stdin.read(): In Python, reading all input at once is faster than repeatedly calling input() when the input is large.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    D = int(input_data[idx]); idx += 1
    A = []
    B = []
    for i in range(N):
        a = int(input_data[idx]); idx += 1
        b = int(input_data[idx]); idx += 1
        A.append(a)
        B.append(b)
    
    best = 0  # 何も注文しない場合は0
    for mask in range(1, 1 << N):
        sa = 0
        sb = 0
        for i in range(N):
            if mask & (1 << i):
                sa += A[i]
                sb += B[i]
        val = sa - D * max(0, sb - K)
        if val > best:
            best = val
    
    print(best)

main()

---

This editorial was generated by claude4.6opus-thinking.