Overview

Given \(N\) cards, select exactly \(K\) cards to flip over, and maximize the sum of the numbers visible on the face-up side.

Analysis

Each card has a front value \(F_i\) and a back value \(B_i\). Initially, all cards are face-up, and the goal is to maximize the sum of visible values by flipping exactly \(K\) cards.

A straightforward approach is to try all possible ways to choose \(K\) cards. Since \(N\) is at most \(20\), the number of combinations \({}_N C_K\) is small enough even when choosing from \(20\) cards, making exhaustive search feasible.

For example, flipping the \(i\)-th card results in a score change of \(B_i - F_i\). In other words, we can compute the “profit” from flipping each card and it might seem optimal to select the top \(K\) cards with the highest profit. However, this greedy approach is not always correct (especially when \(K=0\) or when all profits are negative). Therefore, a safe and reliable approach is to try all combinations.

Algorithm

1. Read the front value \(F_i\) and back value \(B_i\) for all cards.
2. For every combination of choosing \(K\) cards from \(N\) cards, do the following:
   • For selected cards, add the back value \(B_i\); for unselected cards, add the front value \(F_i\).
   • Record the total and update the maximum value found so far.
3. Output the maximum value.

Specifically, using Python’s itertools.combinations, we generate all combinations of choosing \(K\) indices from \(0\) to \(N-1\).

For example, if there are 3 cards with card information (3, 5), (2, 8), (4, 1) and \(K = 2\): - Select cards 0 and 1: \(5 + 8 + 4 = 17\) - Select cards 0 and 2: \(5 + 2 + 1 = 8\) - Select cards 1 and 2: \(3 + 8 + 1 = 12\)

The maximum among these is \(17\).

Complexity

• Time complexity: \(O\left(\binom{N}{K} \cdot N\right)\)
  For each of the \(\binom{N}{K}\) combinations, a loop of \(N\) iterations is needed.
• Space complexity: \(O(N)\)
  \(O(N)\) is needed to store the card information.

Given the constraint \(N \leq 20\), the worst case is \(\binom{20}{10} \approx 184756\) combinations, which runs sufficiently fast.

Implementation Notes

• By using combinations(range(N), K), we can easily enumerate all ways to choose \(K\) cards.

• For each combination, determine whether each card is selected and add either the front or back value accordingly.

• It is easier to implement by initially treating all cards as face-up, then switching only the selected ones to face-down.

  Source Code

from itertools import combinations

N, K = map(int, input().split())
cards = [tuple(map(int, input().split())) for _ in range(N)]

max_sum = 0

for selected_cards in combinations(range(N), K):
    current_sum = 0
    for i in range(N):
        if i in selected_cards:
            current_sum += cards[i][1]  # 裏面
        else:
            current_sum += cards[i][0]  # 表面
    max_sum = max(max_sum, current_sum)

print(max_sum)

This editorial was generated by qwen3-coder-480b.