Overview

When selecting at most \(K\) types of flowers, we want to find the maximum value of the total beauty of selected flowers plus the total prize money from contests whose conditions are satisfied (at least one flower is selected within the contest’s interval). Since \(N \le 15\) is small, we can enumerate all possible flower selections as bit sets (subsets).

Analysis

Key Observations

• Selecting or not selecting each flower is a binary choice, so there are \(2^N\) total possible selections.
• Since \(N \le 15\), we have \(2^{15}=32768\), which is small enough to enumerate all subsets and evaluate each one.
• Each contest \(j\) has the condition “prize \(P_j\) is awarded if at least one flower in the interval \([L_j, R_j]\) is selected.” This can be checked as whether the selected set and the set of flowers in the interval share a common element, which translates to a bitwise operation:
  • Condition satisfied \(\Leftrightarrow\) mask & cmask != 0

What Goes Wrong with a Naive Approach

• For example, if we scan all \(N\) flowers for each subset to compute the beauty sum, the total complexity becomes \(O(2^N \cdot N)\). This is fast enough for this problem, but as an optimization, reusing beauty sums via subset DP leads to cleaner implementation.
• For contest checking, scanning the interval \([L, R]\) each time is wasteful. By precomputing the interval as a bitmask, the check reduces to a single & operation.

How to Solve It

• Represent the set of flowers as a bitmask mask of length \(N\) (bit \(i\) is 1 if flower \(i\) is selected).
• Convert each contest’s interval \([L_j, R_j]\) into a bitmask cmask in advance.
• For each mask:
  • If the number of selected flowers is at most \(K\) (mask.bit_count() <= K):
  • Compute the beauty sum + total prize money from satisfied contests, and update the maximum.

(Example) For \(N=5\), selecting flowers {2, 4} gives mask = 01010(2). If a contest’s interval is \([3, 5]\), then cmask = 11100(2). Here mask & cmask = 01000(2), which is not 0, so the condition is satisfied and the prize money can be added.

Algorithm

1. Read the input.
2. For each contest \(j\), convert the interval \([L_j, R_j]\) into a bitmask cmask and store it as (cmask, P_j).
3. Precompute the beauty sum beauty[mask] for all subsets mask = 0 .. 2^N-1.
   • Extract the lowest set bit lsb of mask, determine the flower \(i\) it represents, and use the recurrence: \(beauty[mask] = beauty[mask \setminus \{i\}] + S_i\) (in code: beauty[mask ^ lsb] + S[i]).
4. Enumerate all mask values, skipping those where the number of selected flowers exceeds \(K\).
5. Set total = beauty[mask], and for each contest:
   • If mask & cmask != 0, then total += P
6. Output the maximum value of total as the answer.

Complexity

• Time complexity: Beauty precomputation is \(O(2^N)\), and contest checking for each subset is \(O(M)\), so the total is \(O(2^N \cdot M + 2^N) = O(2^N \cdot M)\)
• Space complexity: The beauty array beauty is \(O(2^N)\), and storing contests is \(O(M)\), so \(O(2^N)\)

Implementation Notes

• Converting the interval \([L, R]\) to a bitmask allows the condition check to be done in a single mask & cmask operation.

• mask.bit_count() (Python 3.8+) efficiently counts the number of selected flowers.

• Precomputing beauty sums using the lsb-based update (subset DP) is more concise than summing all \(N\) elements each time.

• “Selecting nothing (mask=0)” is also allowed, and its value is 0, so initializing the answer to 0 handles this case naturally.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K, M = map(int, input().split())
    S = list(map(int, input().split()))
    contests = []
    for _ in range(M):
        L, R, P = map(int, input().split())
        mask = 0
        for i in range(L - 1, R):
            mask |= 1 << i
        contests.append((mask, P))

    size = 1 << N
    beauty = [0] * size
    for mask in range(1, size):
        lsb = mask & -mask
        i = lsb.bit_length() - 1
        beauty[mask] = beauty[mask ^ lsb] + S[i]

    ans = 0
    for mask in range(size):
        if mask.bit_count() > K:
            continue
        total = beauty[mask]
        for cmask, p in contests:
            if mask & cmask:
                total += p
        if total > ans:
            ans = total

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.