Overview

Since the number of flower types \(N\) is at most 15, which is small, this problem can be solved using bit brute-force that tries all possible ways of selecting flowers.

Analysis

In this problem, we need to select at most \(K\) types of flowers and maximize the sum of their beauty values plus the total prize money from contests we can participate in based on the selected flowers. The participation condition for a contest is that at least one flower within a specific interval \([L_j, R_j]\) must be selected.

Since the constraints on \(N\) and \(M\) are at most 15, which is small, we can try all possible ways of selecting flowers (\(2^N\) possibilities). For each selection, we check the total beauty of the selected flowers and whether the participation conditions for each contest are satisfied, adding the prize money accordingly, to find the maximum value.

Algorithm

1. Represent the flower selection as a bitmask and try all values from \(0\) to \(2^N - 1\).
2. For each bitmask, check whether the number of selected flowers is at most \(K\).
3. Calculate the total beauty of the selected flowers.
4. For each contest, check whether at least one flower within the interval \([L_j, R_j]\) is selected. If so, add the contest’s prize money \(P_j\).
5. Compute the sum of total beauty and total prize money, and update the maximum value.

Complexity

• Time complexity: \(O(2^N \times M \times N)\)
  • There are \(2^N\) bitmasks, for each bitmask we check \(M\) contests, and the length of each contest’s interval is at most \(N\).
• Space complexity: \(O(N + M)\)
  • Memory for storing the input data.

Implementation Notes

• Each bit of the bitmask corresponds to the selection of a flower. If a bit is set, it means that flower is selected.

• Contest intervals are handled by adjusting to 0-indexed.

• The case where no flowers are selected (bitmask is 0) is also considered. In this case, both the total beauty and total prize money are 0.

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    
    idx = 0
    N = int(data[idx]); K = int(data[idx+1]); M = int(data[idx+2]); idx += 3
    S = list(map(int, data[idx:idx+N])); idx += N
    contests = []
    for i in range(M):
        L = int(data[idx]); R = int(data[idx+1]); P = int(data[idx+2]); idx += 3
        contests.append((L-1, R-1, P))  # 0-indexedに調整
    
    ans = 0
    # すべての花の選び方（ビットマスク）を試す
    for bitmask in range(1 << N):
        count = bin(bitmask).count('1')
        if count > K:
            continue
            
        total_s = 0
        # 美しさの合計を計算
        for i in range(N):
            if bitmask & (1 << i):
                total_s += S[i]
                
        total_p = 0
        # 各コンテストについて参加条件を満たすかチェック
        for (L, R, P) in contests:
            found = False
            for i in range(L, R+1):
                if bitmask & (1 << i):
                    found = True
                    break
            if found:
                total_p += P
                
        total = total_s + total_p
        if total > ans:
            ans = total
            
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by deepseekv3.