Overview

We treat products as a weighted point sequence and advertising campaigns as intervals, and find the maximum weight of the union when exactly \(K\) intervals are selected.

After removing interval containment relationships, we solve it in \(O(M \log M + KM)\) using DP with the two-pointer technique and a monotone queue.

Analysis

“Exactly \(K\)” can be treated as “at most \(K\)”

All product profits \(V_i\) are positive.

Therefore, even if we add a campaign, the set of products sold only expands or stays the same, and the total profit never decreases.

Thus,

• The maximum when selecting at most \(K\)
• The maximum when selecting exactly \(K\)

are the same.

Even if the optimal solution with at most \(K\) uses fewer than \(K\) campaigns, we can add arbitrary campaigns without decreasing profit, adjusting to exactly \(K\).

---

Contained intervals are unnecessary

For example, suppose one campaign’s interval is \([2, 5]\) and another’s is \([3, 4]\).

Here, \([3, 4]\) is completely contained in \([2, 5]\).

Rather than selecting \([3, 4]\), selecting \([2, 5]\) instead will not decrease profit.

Therefore, intervals completely contained in other intervals can be removed when finding the optimal value.

Sort the intervals by:

• Ascending order of left endpoint \(L\)
• Descending order of right endpoint \(R\) if left endpoints are the same

Then, scanning from left to right, keep only intervals whose right endpoint is larger than the maximum right endpoint seen so far.

After this, for the remaining intervals:

\[ L_0 < L_1 < \cdots < L_{m-1} \]

and

\[ R_0 < R_1 < \cdots < R_{m-1} \]

hold.

In other words, the remaining intervals have both left and right endpoints monotonically increasing.

---

A naive DP is too slow

Let \(m\) be the number of remaining intervals.

Define \(dp_t[i]\) as:

The maximum profit when selecting \(t\) intervals, with the last selected interval being \(i\).

If we let \(j\) be the interval selected immediately before interval \(i\), naively trying all \(j < i\) costs \(O(m^2)\) for each \(t\).

Even though \(K \leq 10\), \(m\) can be up to \(10^5\), so \(O(Km^2)\) is too slow.

We optimize the transitions to achieve \(O(Km)\).

---

Incremental gain when adding an interval

Define the prefix sum as:

\[ S_i = V_1 + V_2 + \cdots + V_i \]

If interval \(i\) is \([L_i, R_i]\), the profit of that interval alone is:

\[ S_{R_i} - S_{L_i - 1} \]

Let us define:

\[ A_i = S_{L_i - 1} \]

\[ B_i = S_{R_i} \]

Consider selecting interval \(i\) after interval \(j\).

Since the remaining intervals have both \(L\) and \(R\) increasing, if \(j < i\) then:

\[ L_j < L_i,\quad R_j < R_i \]

1. When intervals \(j\) and \(i\) do not overlap

If

\[ R_j < L_i \]

then interval \(i\) contributes entirely new profit.

The increment is:

\[ B_i - A_i \]

2. When intervals \(j\) and \(i\) overlap

If

\[ R_j \geq L_i \]

then the portion \([L_i, R_j]\) of interval \(i\) is already covered by interval \(j\).

Therefore, the newly added portion is from \(R_j+1\) to \(R_i\), and the increment is:

\[ B_i - B_j \]

---

DP transition formula

From the above, \(dp_t[i]\) can be expressed as:

\[ dp_t[i] = \max_{j < i} \begin{cases} dp_{t-1}[j] + B_i - A_i & (R_j < L_i) \\ dp_{t-1}[j] + B_i - B_j & (R_j \geq L_i) \end{cases} \]

Rearranging:

\[ dp_t[i] = B_i + \max \left( \max_{j < i, R_j < L_i}(dp_{t-1}[j] - A_i), \max_{j < i, R_j \geq L_i}(dp_{t-1}[j] - B_j) \right) \]

Here, since \(A_i\) is fixed for each \(i\), the first part requires computing:

\[ \max_{j < i, R_j < L_i} dp_{t-1}[j] - A_i \]

And the second part requires computing:

\[ \max_{j < i, R_j \geq L_i}(dp_{t-1}[j] - B_j) \]

---

Optimization

In the remaining intervals, \(R_i\) is monotonically increasing.

Therefore, for each \(i\), the maximum range satisfying

\[ R_j < L_i \]

consists of intervals before some position \(p\).

That is:

• \(j < p\): does not overlap with interval \(i\)
• \(p \leq j < i\): overlaps with interval \(i\)

Maximum over non-overlapping intervals

We need:

\[ \max_{j < p} dp_{t-1}[j] \]

This can be computed in \(O(1)\) by maintaining a prefix maximum pref_dp.

Maximum over overlapping intervals

We need:

\[ \max_{p \leq j < i}(dp_{t-1}[j] - B_j) \]

This is the maximum over the range \([p, i-1]\).

As \(i\) increases, both the left and right endpoints of this range only move to the right, so using a monotone queue allows processing the entire thing in \(O(m)\).

Algorithm

1. Compute the prefix sum \(S\).
2. Sort intervals by \((L, -R)\).
   • This gives ascending \(L\), and descending \(R\) for the same \(L\).
3. Scan from left and keep only intervals whose \(R\) is larger than the maximum right endpoint seen so far.
   • This removes contained intervals.
4. For the remaining intervals, prepare arrays:
   • Ls[i] = L_i
   • Rs[i] = R_i
   • SL[i] = S_{L_i - 1}
   • SR[i] = S_{R_i}
5. Initialize the DP for selecting just 1 interval:

\[ dp[i] = SR[i] - SL[i] \]

1. Perform DP while increasing the number of selected intervals from \(2\) to \(\min(K, m)\):
   • pref_dp[i] = max(dp[0], ..., dp[i])
   • minus[i] = dp[i] - SR[i]
   • Use a monotone queue to manage the maximum of minus among overlapping interval candidates.
2. Update the answer candidate with the maximum at each stage.
3. Output the final maximum.

Complexity

• Time complexity: \(O(M \log M + KM)\)
  • Sorting intervals: \(O(M \log M)\)
  • DP: \(O(Km)\), where \(m \leq M\)
• Space complexity: \(O(M)\)

Implementation Notes

• The total profit can be as large as \(10^5 \times 10^9 = 10^{14}\), so 64-bit integers are necessary.
  • In Python, int handles this without issues.
• The profit of interval \([L, R]\) is computed using the prefix sum as:

\[ S_R - S_{L-1} \]

• For overlap detection between intervals, since product indices are integers:

\[ R_j < L_i \]

means non-overlapping.

When \(R_j = L_i\), product \(L_i\) is shared, so it is treated as overlapping.

• The number of remaining intervals \(m\) after removal may be less than \(K\).

  • In that case, performing DP up to \(\min(K, m)\) intervals is sufficient.

  • In the original problem, we can “additionally select” removed intervals to adjust to exactly \(K\).

    Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M, K = data[0], data[1], data[2]

    pref = [0] * (N + 1)
    acc = 0
    idx = 3
    for i in range(1, N + 1):
        acc += data[idx]
        pref[i] = acc
        idx += 1

    intervals = [(data[i], -data[i + 1]) for i in range(idx, idx + 2 * M, 2)]
    intervals.sort()

    Ls = []
    Rs = []
    SL = []
    SR = []

    max_r = 0
    for l, nr in intervals:
        r = -nr
        if r > max_r:
            Ls.append(l)
            Rs.append(r)
            SL.append(pref[l - 1])
            SR.append(pref[r])
            max_r = r

    m = len(Ls)

    dp = [SR[i] - SL[i] for i in range(m)]
    ans = max(dp)

    limit = min(K, m)
    NEG = -10 ** 30

    for _ in range(2, limit + 1):
        pref_dp = [0] * m
        minus = [0] * m

        mx = NEG
        for i in range(m):
            v = dp[i]
            if v > mx:
                mx = v
            pref_dp[i] = mx
            minus[i] = v - SR[i]

        cur = [NEG] * m
        q = [0] * m
        head = 0
        tail = 0
        p = 0
        layer_max = NEG

        for i in range(m):
            if i:
                add = i - 1
                val = minus[add]
                while tail > head and minus[q[tail - 1]] <= val:
                    tail -= 1
                q[tail] = add
                tail += 1

            li = Ls[i]
            while Rs[p] < li:
                p += 1

            while head < tail and q[head] < p:
                head += 1

            best = NEG
            if p > 0:
                v = pref_dp[p - 1] - SL[i]
                if v > best:
                    best = v
            if head < tail:
                v = minus[q[head]]
                if v > best:
                    best = v

            val = SR[i] + best
            cur[i] = val
            if val > layer_max:
                layer_max = val

        if layer_max > ans:
            ans = layer_max
        dp = cur

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.