算法

(贪心) $O(nm)$

先把所有可利用的行李箱按容量的大小从小到大排序。对于每个行李箱，我们可以从所有未使用的行李中贪心地选择价值最大且当前行李箱能容纳的行李。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::max;
using std::pair;
using std::vector;
using P = pair<int, int>;

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    vector<int> w(n), v(n);
    rep(i, n) cin >> w[i] >> v[i];
    vector<int> x(m);
    rep(i, m) cin >> x[i];

    rep(qi, q) {
        int l, r;
        cin >> l >> r;
        --l; --r;
        vector<int> as;
        rep(i, m) if (i < l or r < i) as.push_back(x[i]);
        sort(as.begin(), as.end());
        vector<bool> used(n);
        int ans = 0;
        for (int a : as) {
            P best(-1, -1);
            rep(i, n) {
                if (used[i]) continue;
                if (w[i] > a) continue;
                best = max(best, P(v[i], i));
            }
            int i = best.second;
            if (i == -1) continue;
            used[i] = true;
            ans += v[i];
        }
        cout << ans << '\n';
    }

    return 0;
}