Overview

For each query \([L,R]\), we need to find the maximum value of a “0/1 knapsack with interval constraints.”
Since \(Q\) is very large, solving each query independently with DP would be too slow, so we speed things up using divide and conquer on intervals + precomputation of knapsack DP.

Analysis

A naive approach would be to run a 0/1 knapsack DP (\(O((R-L+1)M)\)) using only the items in the interval \([L_j, R_j]\) for each query.
However, in the worst case \(N=300,\ M=500,\ Q=10^5\), so this is roughly \(O(QNM)\), which is far too large and results in TLE.

The key observations are:

• \(N\) and \(M\) are relatively small (\(300, 500\))
• \(Q\) is very large (\(10^5\))

This means we need a design that processes queries in bulk.

Divide and Conquer Idea

We split the interval \([L,R]\) at the midpoint \(mid\).
Queries then fall into three categories:

1. Entirely on the left (\(r \le mid\)) → recurse on the left
2. Entirely on the right (\(l > mid\)) → recurse on the right
3. Spanning \(mid\) (\(l \le mid < r\)) → answer on the spot

To answer spanning queries efficiently, we precompute the following:

• Left DP: “maximum value with budget \(\le w\)” for items in \([i..mid]\)
• Right DP: “maximum value with budget \(\le w\)” for items in \([mid+1..i]\)

If a query \([l,r],X\) spans \(mid\), let: - \(A\) be the DP array for the left portion \([l..mid]\) - \(B\) be the DP array for the right portion \([mid+1..r]\)

Then the answer is:

[ \max_{0 \le w \le X} \left(A[w] + B[X-w]\right) ]

This is simply an exhaustive search over how to split the budget between the left and right portions.

With this method, each query is classified exactly once at each level of the recursion tree, and the merge computation is performed exactly once at the moment it spans the midpoint.

Algorithm

1. Read item information \((H_i, V_i)\) and queries \((L_j, R_j, X_j)\).
2. Execute solve(L, R, qids) recursively (qids is the set of query IDs belonging to this interval).
3. Base case:
   • When \(L = R\), we only need to consider that single item.
     If the budget is sufficient, the answer is \(V_L\); otherwise, it is \(0\).
4. Compute the midpoint \(mid\).
5. Build the left DP:
   • Add items one by one in the order i = mid, mid-1, ..., L using 0/1 knapsack.
   • Save intermediate results so that dpl[mid-i] is the DP array for the interval \([i..mid]\).
6. Build the right DP:
   • Similarly, add items in the order i = mid+1, ..., R.
   • dpr[i-(mid+1)] is the DP array for the interval \([mid+1..i]\).
7. Classify each query into three types:
   • Left only / right only queries are forwarded to the corresponding recursive call.
   • For spanning queries, retrieve A = dpl[mid-l] and B = dpr[r-(mid+1)], then compute the maximum of A[w] + B[X-w] for w = 0..X and store the answer.
8. Recurse on left and right.
9. Finally, output answers in the original query order.

Complexity

• Time complexity: \(O(NM\log N + QM\log N)\)
  (At each recursive node, DP construction costs interval length \(\times M\), and processing spanning queries costs \(O(M)\) per query.)
• Space complexity: approximately \(O(NM)\) (DP arrays used at each level of recursion; in practice, allocated on the fly).

Implementation Notes

• Values \(V_i\) can be up to \(10^9\), and their sums can be even larger, so use long long.

• The 0/1 knapsack update must iterate in reverse order: for (w = M; w >= H[i]; --w).

• Be careful with index mapping for dpl[mid-l] and dpr[r-(mid+1)], as it is easy to make mistakes.

• To preserve the output order of queries, assign an idx at input time and write results to ans[idx].

  Source Code

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

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];
    }

    // prefix[l][r][w] equivalent storage:
    // leftDP[l][w] = best for items [l..mid]
    // rightDP[r][w] = best for items [mid+1..r]
    // We'll do divide & conquer on index range and answer queries crossing mid.
    struct Query {
        int l, r, x, idx;
    };
    vector<Query> queries(Q);
    for (int i = 0; i < Q; i++) {
        cin >> queries[i].l >> queries[i].r >> queries[i].x;
        queries[i].idx = i;
    }

    vector<long long> ans(Q, 0);

    function<void(int,int,vector<int>&)> solve = [&](int L, int R, vector<int>& qids) {
        if (qids.empty()) return;
        if (L == R) {
            for (int qi : qids) {
                ans[queries[qi].idx] = (queries[qi].x >= H[L] ? V[L] : 0LL);
            }
            return;
        }

        int mid = (L + R) >> 1;

        // Build DP from mid to L
        int leftLen = mid - L + 1;
        vector<vector<long long>> dpl(leftLen, vector<long long>(M + 1, 0));
        {
            vector<long long> cur(M + 1, 0);
            for (int i = mid, t = 0; i >= L; --i, ++t) {
                for (int w = M; w >= H[i]; --w) {
                    cur[w] = max(cur[w], cur[w - H[i]] + V[i]);
                }
                dpl[t] = cur; // corresponds to segment [i..mid]
            }
        }

        // Build DP from mid+1 to R
        int rightLen = R - mid;
        vector<vector<long long>> dpr(rightLen, vector<long long>(M + 1, 0));
        {
            vector<long long> cur(M + 1, 0);
            for (int i = mid + 1, t = 0; i <= R; ++i, ++t) {
                for (int w = M; w >= H[i]; --w) {
                    cur[w] = max(cur[w], cur[w - H[i]] + V[i]);
                }
                dpr[t] = cur; // corresponds to segment [mid+1..i]
            }
        }

        vector<int> leftQ, rightQ;
        leftQ.reserve(qids.size());
        rightQ.reserve(qids.size());

        for (int qi : qids) {
            auto &qq = queries[qi];
            if (qq.r <= mid) {
                leftQ.push_back(qi);
            } else if (qq.l > mid) {
                rightQ.push_back(qi);
            } else {
                // crossing mid: [qq.l..mid] + [mid+1..qq.r]
                const auto &A = dpl[mid - qq.l];
                const auto &B = dpr[qq.r - (mid + 1)];
                int X = qq.x;
                long long best = 0;
                for (int w = 0; w <= X; ++w) {
                    best = max(best, A[w] + B[X - w]);
                }
                ans[qq.idx] = best;
            }
        }

        if (!leftQ.empty()) solve(L, mid, leftQ);
        if (!rightQ.empty()) solve(mid + 1, R, rightQ);
    };

    vector<int> allQ(Q);
    iota(allQ.begin(), allQ.end(), 0);
    solve(1, N, allQ);

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

    return 0;
}

---

This editorial was generated by gpt-5.3-codex.