Overview

This problem is a “range-restricted 0/1 knapsack problem” where, given item ranges \([L_j, R_j]\) and budgets \(X_j\), we need to find the maximum satisfaction. While the number of items \(N\) and the budget limit \(M\) are relatively small, the number of queries \(Q\) is very large, so performing dynamic programming (DP) independently for each query will not be fast enough.

Analysis

Naive Approach

Solving the knapsack problem for a single query takes \(O(N \times M)\) time. Repeating this \(Q\) times gives an overall complexity of \(O(Q \times N \times M)\). Substituting the constraints: \(10^5 \times 300 \times 500 = 1.5 \times 10^{10}\), which far exceeds the time limit (typically around 2 seconds).

Key Insight for Optimization

The crux of this problem lies in “how to efficiently handle a large number of range queries on static, fixed data”. Since the arrangement of items is fixed, we can use Divide and Conquer to consolidate overlapping computations and reduce the per-query complexity.

Algorithm

We use “Divide and Conquer” to process queries recursively.

1. Divide and Conquer Mechanism

Consider a function solve(L, R, queries). This function processes all queries that are completely contained within the range \([L, R]\).

1. Determine the midpoint \(mid = (L+R)/2\).
2. Classify queries into the following three categories:
   • Queries completely contained in the left half \([L, mid]\)
   • Queries completely contained in the right half \([mid+1, R]\)
   • Queries that cross \(mid\) (\(L_j \le mid\) and \(R_j > mid\))
3. Queries completely contained in the left or right half are processed by recursively calling solve.
4. Queries that cross \(mid\) are processed collectively in this step.

2. Processing Crossing Queries (Merge)

A query \([L_j, R_j]\) that crosses \(mid\) can be decomposed into a “left fragment \([L_j, mid]\)” and a “right fragment \([mid+1, R_j]\)”.

• Left-side preparation: Compute knapsack DP (suffix DP) from \(mid\) going leftward (\(mid, mid-1, \ldots, L\)), for each starting position.
• Right-side preparation: Compute knapsack DP (prefix DP) from \(mid+1\) going rightward (\(mid+1, mid+2, \ldots, R\)), for each ending position.
• Combination: Given a query’s budget \(X_j\), we try all \(0 \le k \le X_j\), where we spend budget \(k\) on the left side and budget \(X_j - k\) on the right side, and take the maximum sum of satisfactions. This gives the answer for that query.

This combination step takes \(O(M)\) per query.

Complexity

• DP table construction: At each level of the divide and conquer, we perform DP over all \(N\) items. The depth of recursion is \(O(\log N)\), so the total is \(O(N \times M \times \log N)\).

• Query processing: Each query is processed exactly once at the level where it crosses some \(mid\). The combination step costs \(O(M)\), so the total is \(O(Q \times M)\).

• Total time complexity: \(O(N M \log N + QM)\) Substituting the constraints gives approximately \(1.2 \times 10^6 + 5 \times 10^7\), which comfortably fits within the time limit.

• Space complexity: \(O(NM + Q)\) We need to maintain DP tables at each level of recursion.

Implementation Notes

• DP table management: cur_dp_l[i][w] holds “the maximum satisfaction using items from \(i\) to \(mid\) with weight at most \(w\)”. To save memory, reuse 1D arrays or allocate only as much as needed.

• Query distribution: At each recursive call, distribute queries into left_q, right_q, and cross_q to avoid unnecessary exploration.

• Fast I/O: Since \(Q=10^5\) is large, in C++ it is advisable to use cin.tie(NULL); ios::sync_with_stdio(false); and use \n instead of endl.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Structure to store item properties: price (h) and satisfaction (v)
struct Item {
    int h;
    long long v;
};

// Structure to store query details: range [l, r], budget (x), and original index (id)
struct Query {
    int l, r, x, id;
};

int N, M, Q;
Item items[305];
long long results[100005];

/**
 * Solves the range knapsack problem using a Divide and Conquer approach.
 * This handles queries by splitting the range and processing those that cross the midpoint.
 * 
 * Time Complexity: O(N * M * log N + Q * M)
 * Space Complexity: O(N * M + Q)
 */
void solve(int L, int R, const vector<Query>& queries) {
    // If no queries are in this range, return early
    if (queries.empty()) return;

    // Base case: range consists of a single item
    if (L == R) {
        for (const auto& q : queries) {
            // Only one item to consider, check if budget allows it
            results[q.id] = (items[L].h <= q.x ? items[L].v : 0);
        }
        return;
    }

    int mid = (L + R) / 2;
    vector<Query> left_q, right_q, cross_q;

    // Distribute queries into three groups based on their range [l, r]
    for (const auto& q : queries) {
        if (q.r <= mid) {
            left_q.push_back(q);
        } else if (q.l > mid) {
            right_q.push_back(q);
        } else {
            cross_q.push_back(q);
        }
    }

    // Process queries that cross the midpoint
    if (!cross_q.empty()) {
        int l_size = mid - L + 2;
        int r_size = R - mid + 1;
        int m_plus_1 = M + 1;

        // DP tables for the suffix of the left side and prefix of the right side
        // cur_dp_l[i - L] stores the knapsack for items [i, mid]
        // cur_dp_r[i - mid] stores the knapsack for items [mid + 1, i]
        vector<long long> cur_dp_l(l_size * m_plus_1, 0);
        vector<long long> cur_dp_r(r_size * m_plus_1, 0);

        // Compute suffix knapsacks for the left side [L, mid]
        for (int i = mid; i >= L; --i) {
            int idx = i - L;
            int next_idx = idx + 1;
            int cur_base = idx * m_plus_1;
            int next_base = next_idx * m_plus_1;
            int h = items[i].h;
            long long v = items[i].v;
            for (int w = 0; w < h; ++w) {
                cur_dp_l[cur_base + w] = cur_dp_l[next_base + w];
            }
            for (int w = h; w <= M; ++w) {
                long long val1 = cur_dp_l[next_base + w];
                long long val2 = cur_dp_l[next_base + w - h] + v;
                cur_dp_l[cur_base + w] = (val1 > val2 ? val1 : val2);
            }
        }

        // Compute prefix knapsacks for the right side [mid + 1, R]
        for (int i = mid + 1; i <= R; ++i) {
            int idx = i - mid;
            int prev_idx = idx - 1;
            int cur_base = idx * m_plus_1;
            int prev_base = prev_idx * m_plus_1;
            int h = items[i].h;
            long long v = items[i].v;
            for (int w = 0; w < h; ++w) {
                cur_dp_r[cur_base + w] = cur_dp_r[prev_base + w];
            }
            for (int w = h; w <= M; ++w) {
                long long val1 = cur_dp_r[prev_base + w];
                long long val2 = cur_dp_r[prev_base + w - h] + v;
                cur_dp_r[cur_base + w] = (val1 > val2 ? val1 : val2);
            }
        }

        // Combine the results from the left suffix and right prefix for crossing queries
        for (const auto& q : cross_q) {
            long long max_v = 0;
            int l_base = (q.l - L) * m_plus_1;
            int r_base = (q.r - mid) * m_plus_1;
            for (int k = 0; k <= q.x; ++k) {
                long long current_v = cur_dp_l[l_base + k] + cur_dp_r[r_base + (q.x - k)];
                if (current_v > max_v) max_v = current_v;
            }
            results[q.id] = max_v;
        }
    }

    // Recursively solve for queries strictly in the left or right halves
    solve(L, mid, left_q);
    solve(mid + 1, R, right_q);
}

int main() {
    // Optimize I/O operations
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N >> M >> Q)) return 0;

    // Input items (1-indexed)
    for (int i = 1; i <= N; ++i) {
        cin >> items[i].h >> items[i].v;
    }

    // Input queries
    vector<Query> queries(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> queries[i].l >> queries[i].r >> queries[i].x;
        queries[i].id = i;
    }

    // Solve using divide and conquer
    solve(1, N, queries);

    // Output all query results
    for (int i = 0; i < Q; ++i) {
        cout << results[i] << "\n";
    }

    return 0;
}

---

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