Overview

Given \(N\) cards, the problem asks you to choose exactly \(K\) cards to flip over and maximize the total of the visible numbers on all cards.

Analysis

Key Observation

For each card, there are two choices: flip it or don’t flip it. If flipped, the back value \(B_i\) is added to the total; if not flipped, the front value \(F_i\) is added. However, exactly \(K\) cards must be flipped.

Is a Naive Approach Sufficient?

The number of ways to choose \(K\) cards from \(N\) is \(\binom{N}{K}\). Since \(N \leq 20\), this is at most around \(\binom{20}{10} = 184,756\). Computing the total for each combination takes \(O(N)\), but the overall number of operations is only on the order of a few million, so brute-force enumeration is fast enough.

Concrete Example

For example, with \(N = 3, K = 1\) and cards \((F, B) = (10, 5), (3, 8), (7, 7)\):

• Flip card 1 → \(5 + 3 + 7 = 15\)
• Flip card 2 → \(10 + 8 + 7 = 25\) ← maximum
• Flip card 3 → \(10 + 3 + 7 = 20\)

In this way, we try all ways of choosing \(K\) cards and find the maximum value.

Algorithm

1. Read the information for \(N\) cards.
2. Enumerate all combinations of choosing \(K\) cards from \(N\) (using Python’s itertools.combinations).
3. For each combination, add the back value \(B_i\) for the selected cards and the front value \(F_i\) for the rest, computing the total.
4. Output the maximum total among all combinations.

Complexity

• Time complexity: \(O(\binom{N}{K} \cdot N)\)
  • The number of combinations \(\binom{N}{K}\) is at most \(\binom{20}{10} = 184,756\), and computing the total takes \(O(N)\) per combination, so the maximum number of operations is approximately \(184,756 \times 20 \approx 3.7 \times 10^6\), which is fast enough.
• Space complexity: \(O(N)\)
  • \(O(N)\) is needed to store the card information and the set of flipped cards.

Implementation Notes

• Using itertools.combinations(range(N), K) concisely enumerates all combinations of choosing \(K\) indices from \(0\) to \(N-1\).

• By converting the indices of flipped cards to a set, we can check whether each card is flipped in \(O(1)\).

• The initial value is set to -float('inf'), but even when \(K = 0\), combinations(range(N), 0) returns a single empty tuple, so it works correctly.

  Source Code

from itertools import combinations

N, K = map(int, input().split())
cards = []
for _ in range(N):
    f, b = map(int, input().split())
    cards.append((f, b))

ans = -float('inf')
for flipped in combinations(range(N), K):
    flipped_set = set(flipped)
    total = 0
    for i in range(N):
        if i in flipped_set:
            total += cards[i][1]
        else:
            total += cards[i][0]
    ans = max(ans, total)

print(ans)

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