Overview

This is a problem of finding the maximum value of “total beauty + total prize money” when selecting at most \(K\) types out of \(N\) types of flowers. Since the constraint \(N \le 15\) is very small, we can find the correct answer by trying all possible selections using bit exhaustive search (bitmask enumeration).

Analysis

Since there are \(N\) types of flowers, there are \(2^N\) possible combinations of selecting or not selecting each flower. Normally, when the number of combinations is enormous, it is impossible to try all patterns, but in this problem, the constraint \(N \le 15\) is given. Even when \(N = 15\), there are only \(2^{15} = 32768\) patterns, so exhaustive search can be computed sufficiently fast.

For each selection, we calculate the score using the following procedure: 1. Check whether the number of selected flowers is at most \(K\) types. 2. Calculate the total beauty of the selected flowers. 3. For each contest, check whether the participation condition is satisfied (whether at least one flower in the specified range is included), and if so, add the prize money.

Since the score when nothing is selected is \(0\), we can set the initial maximum value to \(0\) and find the maximum score across all patterns.

Algorithm

We use a technique called bit exhaustive search (bitmask enumeration). This method uses the binary representation of integers to enumerate all combinations of “select / don’t select”.

1. Loop through integers bits from \(0\) to \(2^N - 1\). If the \(i\)-th bit of bits is \(1\), it corresponds to “select flower \(i\)”; if \(0\), “don’t select”.
2. Count the number of \(1\)s in bits (the number of selected flowers). If this exceeds \(K\), the condition is not satisfied, so skip.
3. Sum up the beauty \(S_i\) of the selected flowers.
4. Check the participation conditions for each contest.
   • The condition for contest \(j\), “select at least one flower from \(L_j\) to \(R_j\)”, can be easily checked by precomputing a “bitmask” with the bits in that range set to \(1\).
   • By taking the logical AND (AND operation bits & mask) of bits representing the selection and mask representing the contest condition, if the result is \(1\) or more, we can determine that “at least one flower within the condition’s range is selected”.
5. Add the prize money \(P_j\) of contests whose conditions are satisfied to the total score.
6. Update the maximum value ans with the calculated total score.

Complexity

• Time complexity: \(O(2^N \cdot (N + M))\)
  • There are \(2^N\) ways to select flowers.
  • For each selection, checking the selected flowers takes \(O(N)\) and checking the contest conditions takes \(O(M)\).
  • When \(N, M \le 15\), the total number of operations is approximately \(32768 \times 30 \approx 10^6\), which easily fits within the time limit (typically 2 seconds).
• Space complexity: \(O(N + M)\)
  • This is the memory used to store the list of flower beauties and contest conditions (bitmasks and prize money).

Implementation Notes

• Conversion to 0-indexed The flower numbers given in the input range from \(1\) to \(N\), but to make them easier to handle in the program (arrays and bit shifts), we subtract \(1\) from all of them to convert to indices from \(0\) to \(N-1\) (e.g., L = int(...) - 1).

• Creating bitmasks The bitmask representing the contest condition range \([L, R]\) can be created with ((1 << (R - L + 1)) - 1) << L. For example, when \(L=1, R=3\), the range length is \(3\), so 1 << 3 gives \(8\) (binary 1000), and subtracting \(1\) gives \(7\) (binary 0111). By shifting this left by \(L\) (\(=1\)) bits, the desired mask 1110 is completed.

• Counting set bits In Python, you can concisely obtain the number of selected flowers by combining the bin() method, which converts an integer to a binary string, with the count() method, which counts characters: bin(bits).count('1').

  Source Code

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    K = int(data[1])
    M = int(data[2])
    
    S = [int(x) for x in data[3:3+N]]
    
    contests = []
    idx = 3 + N
    for _ in range(M):
        L = int(data[idx]) - 1
        R = int(data[idx+1]) - 1
        P = int(data[idx+2])
        mask = ((1 << (R - L + 1)) - 1) << L
        contests.append((mask, P))
        idx += 3
        
    ans = 0
    
    for bits in range(1 << N):
        if bin(bits).count('1') > K:
            continue
            
        score = 0
        for i in range(N):
            if (bits >> i) & 1:
                score += S[i]
                
        for mask, P in contests:
            if bits & mask:
                score += P
                
        if score > ans:
            ans = score
            
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.