Overview

Given \(N\) types of flowers (\(N \leq 15\)), select at most \(K\) types to maximize the sum of flower beauty values and contest prize money. Since \(N\) is small, we can enumerate all possible flower selections (bit brute force) to solve the problem.

Analysis

Key Observation

• The constraint \(N \leq 15\) is very small. Since there are \(2\) choices (select or not select) for each of the \(N\) types of flowers, the total number of combinations is only \(2^{15} = 32768\).
• For each combination, we just need to calculate the total beauty and total contest prize money, so full enumeration is well within time limits.

Contest Participation Check

The condition for participating in contest \(j\) (= being required to participate) is “having planted at least \(1\) type of flower with a number between \(L_j\) and \(R_j\) inclusive.”

For example, if \(L_j = 2, R_j = 4\), the participation condition is satisfied if any one of flowers \(2, 3, 4\) is selected.

We perform this check efficiently using bitmasks. We map flower \(i\) (\(1\)-indexed) to bit \(i-1\), and for contest \(j\), we precompute a mask contest_mask[j] with bits set from \(L_j\) to \(R_j\). By taking the AND of the selected flower set flower_set with this mask, we can determine the condition is satisfied if the result is not \(0\).

Concrete Example

\(N = 3\), \(K = 2\), flower beauty values \(S = [-5, 3, 2]\), contest \((L=1, R=2, P=10)\):

• Select flowers \(\{2, 3\}\) → bit representation 110 → beauty \(3+2=5\), contest mask for \(L=1, R=2\) is 011, AND gives `010 \neq 0\( so we participate → total \)5 + 10 = 15$
• Select only flower \(\{3\}\) → bit representation 100 → beauty \(2\), AND with mask 011 gives `000 = 0\( so we don't participate → total \)2$

Algorithm

1. For each contest \(j\), precompute the bitmask contest_mask[j] corresponding to flowers from \(L_j\) to \(R_j\).
2. Enumerate all bitmasks flower_set from \(0\) to \(2^N - 1\).
3. For each flower_set:
   • Check that the number of set bits (number of selected flower types) is at most \(K\). Skip if it exceeds \(K\).
   • Calculate the total beauty of the selected flowers.
   • For each contest, if flower_set & contest_mask[j] is not \(0\), add the prize money \(P_j\).
   • Check if the total of beauty + prize money updates the maximum value.
4. Output the maximum value (include \(0\) as a candidate for the case where no flowers are selected).

Complexity

• Time complexity: \(O(2^N \times (N + M))\)
  • We enumerate \(2^N\) subsets, and for each subset we compute the beauty of \(N\) flowers and check \(M\) contests. Since \(N, M \leq 15\), this is approximately \(32768 \times 30 \approx 10^6\), which is sufficiently fast.
• Space complexity: \(O(N + M)\)

Implementation Notes

• Flowers are given as 1-indexed, but in bitmasks we manage them as 0-indexed, so note that flower \(i\) corresponds to bit \(i-1\).

• The total value when nothing is selected (flower_set = 0) is \(0\). By initializing the maximum to \(0\), the output will correctly be \(0\) even when all flower beauty values are negative and participating in contests would only cause a loss.

• You can easily compute the number of set bits (popcount) using bin(flower_set).count('1').

  Source Code

import sys
from itertools import combinations

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    S = [0] * N
    for i in range(N):
        S[i] = int(input_data[idx]); idx += 1
    
    contests = []
    for j in range(M):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        P = int(input_data[idx]); idx += 1
        contests.append((L, R, P))
    
    # For each contest, precompute the bitmask of flowers that can satisfy it
    # Flower i (1-indexed) corresponds to bit (i-1)
    contest_mask = [0] * M
    for j in range(M):
        L, R, P = contests[j]
        mask = 0
        for i in range(L - 1, R):
            mask |= (1 << i)
        contest_mask[j] = mask
    
    best = 0  # choosing nothing gives 0
    
    # Enumerate all subsets of flowers with size <= K
    # N <= 15, so 2^15 = 32768 subsets
    for flower_set in range(1 << N):
        count = bin(flower_set).count('1')
        if count > K:
            continue
        
        # Sum of beauty
        beauty = 0
        for i in range(N):
            if flower_set & (1 << i):
                beauty += S[i]
        
        # Sum of contest prizes
        prize = 0
        for j in range(M):
            # Contest j is satisfied if flower_set has at least one flower in [L_j, R_j]
            if flower_set & contest_mask[j]:
                prize += contests[j][2]
        
        total = beauty + prize
        if total > best:
            best = total
    
    print(best)

main()

---

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