ABC195-D Shipping Center

条件の厳しいやつからペアを組ませる系
atcoder.jp
【問題】
箱と荷物がある。荷物には重さと価値があり、箱は重さXi以下の荷物を1つしか入れられない。
適切に箱に荷物を詰めて価値を最大化せよ。
ただし、クエリごとに詰められない箱の区間が与えられる。
【典型ポイント】
条件の厳しい順に貪欲
【方針】
直感的に、大きさの小さな箱から順に「詰められる荷物のうち価値が最大の荷物」を割り当てていくのが最適に思える。
ある箱に入れられる荷物はより大きい箱にも入れられるので、なるべく小さい箱に入れたい、というお気持ち
各値が小さいので愚直にシミュレートしても間に合うので、そのままやる。
クエリごとに使えない箱が出てくるが、愚直に取り除いても間に合う。

【感想】
Dで制約が緩いやるだけ問題は珍しいと思った

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
constexpr long long INF = 1000000000 + 100;
constexpr long long LINF = 1000000000000000000 + 100;
#define all(v) v.begin(), v.end()
#define rep(i, n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
#define rrep(i, n) for(int i=(n); i>=0; i--)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



int main(){

    int N, M, Q; cin >> N >> M >> Q;
    vector<pll> nimotu(N); //value, weight
    rep(i, N){
        ll w, v; cin >> w >> v;
        nimotu[i] = {v, w};
    }
    sort(all(nimotu), greater<pll>());
    vector<ll> X(M); rep(i, M)cin >> X[i];

    vector<ll> ans;
    while(Q--){
        int L, R; cin >> L >> R; L--; //[L, R)
        vector<ll> box;
        rep(i, M){
            if(i<L or i>= R)box.push_back(X[i]);
        }
        sort(all(box));

        ll res = 0; vector<int> used(N);
        rep(i, box.size()){
            rep(j, N){
                if(used[j])continue;
                if(nimotu[j].second <= box[i]){
                    res += nimotu[j].first;
                    used[j] = true;
                    break;
                }
            }
        }
        ans.push_back(res);
    }
    for(auto a:ans)cout << a << ln;
}