Overview

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

Since \(K \leq 10\) is small, we perform DP with states being “the number of campaigns selected so far” and “the rightmost position.”

Analysis

First, an important observation: all profits \(V_i\) are positive.

Therefore, selecting additional campaigns can only expand (or maintain) the set of products sold, and profit never decreases.

Thus, we can consider:

“Maximum when selecting exactly \(K\)” = “Maximum when selecting at most \(K\)”

Even if the maximum profit is achieved with fewer than \(K\) campaigns, we can arbitrarily add remaining campaigns without decreasing profit, reaching exactly \(K\).

---

Consider scanning intervals from left to right.

Suppose we have already selected some campaigns, and the rightmost position among products being sold is \(x\).

When newly selecting a campaign \([L, R]\), there are two cases:

1. The previous right endpoint is to the left of the interval’s left endpoint

That is, when \(x < L\).

In this case, the interval \([L, R]\) does not overlap with previously sold products, so the additional profit gained is

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

where \(S_i\) is the prefix sum of profits.

2. The previous right endpoint is inside the interval

That is, when \(L \leq x < R\).

In this case, products from \(L\) to \(x\) are already being sold, so the newly added range is from \(x+1\) to \(R\).

The additional profit is

\[ S_R - S_x \]

---

Naively trying all \(x\) for each campaign \([L, R]\) leads to \(O(KMN)\) in the worst case, which is too slow for \(N, M \leq 10^5\).

Therefore, we efficiently compute the following two types of maximum values:

• Maximum for \(x < L\)
  Compute \(\max dp[x]\) using prefix maximum
• Maximum for \(L \leq x < R\)
  Compute \(\max (dp[x] - S_x)\) using a segment tree

Algorithm

Define the prefix sum as

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

Define the DP as follows:

\[ dp_t[r] \]

represents the maximum profit when \(t\) effective campaigns have been selected and the rightmost position of sold products is \(r\).

The initial state is

\[ dp_0[0] = 0 \]

Since products are numbered from \(1\) to \(N\), position \(0\) represents “nothing has been sold yet.”

---

Consider selecting campaign \([L, R]\) as the last one chosen.

Let the previous right endpoint be \(x\). The transitions are as follows:

Case \(x < L\)

The entire interval \([L, R]\) is newly sold, so

\[ dp_t[R] = \max \left( dp_t[R], dp_{t-1}[x] + S_R - S_{L-1} \right) \]

What we need is

\[ \max_{0 \leq x \leq L-1} dp_{t-1}[x] \]

which can be computed in \(O(1)\) using a prefix maximum pref.

---

Case \(L \leq x < R\)

The newly sold range is from \(x+1\) to \(R\), so

\[ dp_t[R] = \max \left( dp_t[R], dp_{t-1}[x] + S_R - S_x \right) \]

This can be rewritten as

\[ dp_{t-1}[x] - S_x + S_R \]

Since \(S_R\) is fixed for campaign \([L, R]\), what we need is

\[ \max_{L \leq x < R} (dp_{t-1}[x] - S_x) \]

This is computed in \(O(\log N)\) by querying the range maximum on a segment tree.

---

For each \(t = 1, 2, \ldots, K\), we look at all campaigns and update the DP.

The final answer is the maximum over selecting between \(1\) and \(K\) campaigns inclusive.

In the code, ans is updated with the maximum of cur[i] at each stage.

Complexity

• Time complexity: \(O(K(N + M \log N))\)
• Space complexity: \(O(N)\)

Since \(K \leq 10\), this is sufficiently fast.

Implementation Notes

• The total profit can be up to \(10^5 \times 10^9 = 10^{14}\), so long long is used.
• Unreachable DP states are managed with a very small value NEG.
• Using \(1\)-indexed prefix sums makes it easy to compute the profit of interval \([L, R]\) as

$\( S_R - S_{L-1} \)$

• The segment tree stores

$\( dp_{t-1}[i] - S_i \)$

and retrieves the maximum over the range \([L, R)\). - The answer is updated as the maximum over “at most \(K\)” selections. This equals the value for selecting exactly \(K\), since all profits are positive.

Source Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll NEG = -(1LL << 62);

struct SegTree {
    int n;
    vector<ll> dat;

    void build(const vector<ll>& a) {
        int m = (int)a.size();
        n = 1;
        while (n < m) n <<= 1;
        dat.assign(2 * n, NEG);
        for (int i = 0; i < m; i++) dat[n + i] = a[i];
        for (int i = n - 1; i >= 1; i--) {
            dat[i] = max(dat[i << 1], dat[i << 1 | 1]);
        }
    }

    ll prod(int l, int r) {
        ll res = NEG;
        l += n;
        r += n;
        while (l < r) {
            if (l & 1) res = max(res, dat[l++]);
            if (r & 1) res = max(res, dat[--r]);
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    cin >> N >> M >> K;

    vector<ll> S(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        ll v;
        cin >> v;
        S[i] = S[i - 1] + v;
    }

    vector<pair<int, int>> intervals(M);
    for (int i = 0; i < M; i++) {
        cin >> intervals[i].first >> intervals[i].second;
    }

    vector<ll> prev(N + 1, NEG), cur(N + 1, NEG);
    vector<ll> pref(N + 1), arr(N + 1);
    prev[0] = 0;

    ll ans = 0;
    SegTree seg;

    for (int k = 1; k <= K; k++) {
        pref[0] = prev[0];
        for (int i = 1; i <= N; i++) {
            pref[i] = max(pref[i - 1], prev[i]);
        }

        for (int i = 0; i <= N; i++) {
            if (prev[i] <= NEG / 2) arr[i] = NEG;
            else arr[i] = prev[i] - S[i];
        }
        seg.build(arr);

        fill(cur.begin(), cur.end(), NEG);

        for (auto [L, R] : intervals) {
            ll best = NEG;

            if (pref[L - 1] > NEG / 2) {
                best = max(best, pref[L - 1] + S[R] - S[L - 1]);
            }

            if (L < R) {
                ll q = seg.prod(L, R);
                if (q > NEG / 2) {
                    best = max(best, q + S[R]);
                }
            }

            cur[R] = max(cur[R], best);
        }

        for (int i = 1; i <= N; i++) {
            ans = max(ans, cur[i]);
        }

        prev.swap(cur);
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.