Overview

This problem requires solving \(Q\) instances of the 0/1 knapsack problem, where each query uses only the items within the range \([L_j, R_j]\) and has a budget of at most \(X_j\).

While \(Q\) can be as large as \(100000\), \(N \leq 300\) and \(M \leq 500\) are small, so we efficiently compute the knapsack DP for all intervals.

Analysis

If we naively solve the 0/1 knapsack for each query, a single query takes

\(O((R-L+1)M)\)

time.

In the worst case, this is \(O(NM)\) per query, leading to a total of

\(O(QNM)\)

which, given the constraints, amounts to approximately

\(100000 \times 300 \times 500 = 15000000000\)

operations — far too slow.

Instead of thinking per query, we think per interval.

There are at most

\(O(N^2)\)

distinct intervals \([L, R]\).
Since \(N \leq 300\), the number of intervals is approximately \(45000\).

Furthermore, since the budget limit \(M\) is also small at \(500\), computing the knapsack DP collectively for each interval is fast enough.

The key insight is as follows:

For a fixed left endpoint \(L\), as we extend the right endpoint \(R\) through

\(L, L+1, L+2, \ldots, N\)

in order, the DP for interval \([L, R]\) can be constructed by simply adding item \(R\) to the DP for interval \([L, R-1]\).

In other words, we fix the left endpoint \(L\), maintain a single DP array, and perform the 0/1 knapsack update while incrementing the right endpoint one at a time.

Algorithm

First, we group the queries by their intervals.

Specifically, we store the queries for interval \([L, R]\) in bucket[L][R].
For each query, we need the budget \(X\) and the query index id for outputting the answer.

Next, we iterate over all left endpoints \(L\) from \(1\) to \(N\).

For a fixed \(L\), we prepare a DP array:

\(dp[c] =\) the maximum satisfaction achievable using items in the current interval with a budget of at most \(c\)

Initially, since no items have been considered, all values are \(0\).

Then, we increment the right endpoint \(R\) from \(L\) to \(N\).

Let the price of item \(R\) be \(h = H_R\) and its satisfaction be \(v = V_R\). The 0/1 knapsack update is as follows:

for (int c = M; c >= h; c--) {
    dp[c] = max(dp[c], dp[c - h] + v);
}

It is crucial to update \(c\) from the larger values downward.
Updating from the smaller values would risk using the same item multiple times.

After this update, dp[c] represents the maximum satisfaction achievable using only the items in interval \([L, R]\) with a budget of at most \(c\).

Therefore, for the queries stored in bucket[L][R], the answer for a budget \(X\) is simply

dp[X]

We save this in ans[id] corresponding to the query index.

Finally, we output ans in the original input order.

Complexity

• Time complexity: \(O(N^2M + Q)\)
• Space complexity: \(O(M + N^2 + Q)\)

Since \(N \leq 300\) and \(M \leq 500\), \(N^2M\) is approximately \(45000000\), which runs sufficiently fast.

Implementation Notes

Since this is a 0/1 knapsack, the DP update must always iterate the budget from larger to smaller values.

for (int c = M; c >= h; c--) {
    dp[c] = max(dp[c], dp[c - h] + v);
}

Also, since the satisfaction \(V_i\) can be up to \(10^9\) and there can be up to \(300\) items, the total satisfaction may not fit in an int.
Therefore, the DP array and the answers must be stored using the long long type.

Source Code

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

struct Query {
    int x, id;
};

static vector<Query> bucket[305][305];

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

    int N, M, Q;
    cin >> N >> M >> Q;

    vector<int> H(N + 1);
    vector<long long> V(N + 1);

    for (int i = 1; i <= N; i++) {
        cin >> H[i] >> V[i];
    }

    vector<long long> ans(Q);

    for (int i = 0; i < Q; i++) {
        int L, R, X;
        cin >> L >> R >> X;
        bucket[L][R].push_back({X, i});
    }

    for (int L = 1; L <= N; L++) {
        vector<long long> dp(M + 1, 0);

        for (int R = L; R <= N; R++) {
            int h = H[R];
            long long v = V[R];

            for (int c = M; c >= h; c--) {
                dp[c] = max(dp[c], dp[c - h] + v);
            }

            for (const auto &q : bucket[L][R]) {
                ans[q.id] = dp[q.x];
            }
        }
    }

    for (int i = 0; i < Q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.