Overview

This problem asks us to select exactly \(K\) out of \(M\) given campaigns (intervals) and maximize the total profit of products contained in the union of those intervals.

By sorting the campaign intervals in ascending order of their left endpoints and applying dynamic programming (DP) using segment trees, we can correctly handle overlapping profits while efficiently computing the solution.

Analysis

1. Naive Approach and Its Limitations

There are \(\binom{M}{K}\) ways to choose \(K\) campaigns out of \(M\). Under the constraints \(M \le 10^5, K \le 10\), the number of combinations can be as large as \(\binom{10^5}{10} \approx 2.7 \times 10^{43}\), making brute-force enumeration impossible.

Additionally, when selected intervals overlap, we need to efficiently handle counting the profit of overlapping portions only once.

2. Sorting Intervals and Designing the DP

To efficiently handle overlaps, we consider a DP where we sort all campaigns in ascending order of their left endpoint \(L_j\) and decide from left to right whether to select each campaign.

Let \(S\) be the prefix sum of product profits (\(S[i] = \sum_{k=1}^i V_k\)). The total profit of an interval \([L, R]\) can be expressed as \(S[R] - S[L-1]\).

When processing intervals sorted in ascending order of their left endpoints, the relationship between a newly added interval \([L, R]\) and the last previously selected interval (whose right endpoint is \(x\)) can be categorized into the following three patterns:

Pattern 1: No overlap (\(x < L\))

The newly selected interval \([L, R]\) does not overlap with any previously selected interval. The newly gained profit is \(S[R] - S[L-1]\).

Pattern 2: Partial overlap (\(L \le x < R\))

The right endpoint \(x\) of the last selected interval is at least the left endpoint \(L\) and less than the right endpoint \(R\) of the new interval. The overlapping portion \([L, x]\) has already been collected, so the newly gained profit is from the portion \([x+1, R]\), which is \(S[R] - S[x]\).

Pattern 3: Completely contained (\(x \ge R\))

The new interval \([L, R]\) is completely contained within an already selected interval (since we sorted by left endpoint, \(L_{prev} \le L\) and \(R \le x\)). Selecting this interval provides no additional profit and only wastes one of the \(K\) campaign slots, so this transition can be ignored.

---

3. DP Definition and Speedup

Based on the above analysis, we define the following DP table:

• \(dp[j][x]\): The maximum profit when \(j\) campaigns have been selected so far and the right endpoint of the last selected campaign is \(x\).

The transition when adding campaign \([L, R]\) as the \(j\)-th selected campaign, taking the maximum over patterns, is:

\[ dp[j][R] = S[R] + \max \left( \max_{0 \le x < L} (dp[j-1][x]) - S[L-1], \max_{L \le x < R} (dp[j-1][x] - S[x]) \right) \]

Computing this transition naively takes \(O(N)\) per campaign, resulting in \(O(M \cdot N)\) overall, which exceeds the time limit. However, by examining the transition formula carefully, we can prepare the following two segment trees (RMQ: range maximum query) to compute each transition in \(O(\log N)\):

1. Segment tree \(T[j]\): Manages \(T[j][x] = dp[j][x]\).
   • Pattern 1’s \(\max_{0 \le x < L} T[j-1][x]\) can be obtained in \(O(\log N)\).
2. Segment tree \(U[j]\): Manages \(U[j][x] = dp[j][x] - S[x]\).
   • Pattern 2’s \(\max_{L \le x < R} U[j-1][x]\) can be obtained in \(O(\log N)\).

Algorithm

1. Preprocessing:
   • Compute the prefix sum \(S\) of product profits.
   • Sort the campaign intervals \([L_j, R_j]\) in ascending order of their left endpoint \(L_j\).
2. Initialization:
   • Prepare \(K+1\) segment trees \(T[j], U[j]\) and initialize all values to \(-\infty\).
   • As the initial state, having selected \(0\) campaigns with a right endpoint of \(0\) yields a profit of \(0\), so set \(T[0][0] = 0\).
3. DP Transitions:
   • For each campaign \([L, R]\), perform the following operations in order:
     • For \(j = 1, 2, \ldots, K\), query the segment trees for the following values:

          - $val_1 = (\text{query}(T[j-1], 0, L-1)) - S[L-1]$
          - $val_2 = \text{query}(U[j-1], L, R-1)$
          - $dp[j] = S[R] + \max(val_1, val_2)$
       

     • After computing \(dp[j]\) for all \(j\), update the segment trees:

          - $T[j][R] \leftarrow \max(T[j][R], dp[j])$
          - $U[j][R] \leftarrow \max(U[j][R], dp[j] - S[R])$
       

4. Output the Answer:
   • The maximum value of \(dp[j]\) obtained so far (or the maximum value of \(T[K]\)) is the answer.

Complexity

• Time Complexity: \(O(M \log M + K M \log N)\)
  • Sorting the campaigns takes \(O(M \log M)\).
  • For each of the \(M\) campaigns, we loop over \(K\) values and perform segment tree queries and updates (\(O(\log N)\)), so the entire DP transition takes \(O(K M \log N)\). Since \(K \le 10\) is very small, this runs sufficiently fast.
• Space Complexity: \(O(K N + M)\)
  • We maintain \(2(K+1)\) segment trees of size \(O(N)\), so the space complexity is \(O(K N)\), which is well within the memory limit.

Implementation Notes

• 1-based vs. 0-based indexing:

  • Handling the prefix sum \(S\) and product indices with 1-based indexing allows natural expression of terms like \(L-1\) for interval left endpoints, simplifying the implementation.

• Batch processing (timing of updates):

  • When processing each campaign \([L, R]\), we must ensure that the update result of \(dp[j-1]\) obtained from the same campaign does not affect the computation of \(dp[j]\) within the same step. Therefore, we store computation results in temporary variables for each \(j\), and only update the segment trees after all \(j\) values have been computed.

    Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    V = [int(x) for x in input_data[3:3+N]]
    
    S = [0] * (N + 1)
    for i in range(N):
        S[i+1] = S[i] + V[i]
        
    intervals = []
    idx = 3 + N
    for _ in range(M):
        l = int(input_data[idx])
        r = int(input_data[idx+1])
        intervals.append((l, r))
        idx += 2
        
    intervals.sort()
    
    size = 1
    while size < N + 1:
        size *= 2
        
    INF = 10**18
    
    T = [[-INF] * (2 * size) for _ in range(K + 1)]
    U = [[-INF] * (2 * size) for _ in range(K + 1)]
    
    T_0 = T[0]
    curr = size
    T_0[curr] = 0
    while curr > 1:
        curr >>= 1
        T_0[curr] = 0
        
    ans = 0
    dp = [0] * (K + 1)
    
    def query(tree, l, r, size=size, INF=INF):
        if l > r:
            return -INF
        res = -INF
        l += size
        r += size + 1
        while l < r:
            if l & 1:
                if tree[l] > res:
                    res = tree[l]
                l += 1
            if r & 1:
                r -= 1
                if tree[r] > res:
                    res = tree[r]
            l >>= 1
            r >>= 1
        return res

    def update(tree, idx, val, size=size):
        idx += size
        if val > tree[idx]:
            tree[idx] = val
            while idx > 1:
                idx >>= 1
                left = tree[2 * idx]
                right = tree[2 * idx + 1]
                tree[idx] = left if left > right else right

    for L, R in intervals:
        s_R = S[R]
        s_L_minus_1 = S[L - 1]
        
        for j in range(1, K + 1):
            t_tree = T[j-1]
            val1 = query(t_tree, 0, L - 1) - s_L_minus_1
            
            u_tree = U[j-1]
            val2 = query(u_tree, L, R - 1)
            
            best = val1 if val1 > val2 else val2
            dp[j] = s_R + best
            if dp[j] > ans:
                ans = dp[j]
                
        for j in range(1, K + 1):
            val = dp[j]
            if val != -INF:
                update(T[j], R, val)
                update(U[j], R, val - s_R)
                
    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.