[AtCoder] ABC 195 D – Shipping Center

2021年3月21日

問題

方針

価値が高い荷物からその大きさに最も近い箱に入れます。

コード

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

struct Data {
    ll w, v;
    Data(ll w, ll v) : w(w), v(v) {}
    bool operator < (const Data &d) const {
        if (d.v == v) {
            return d.w > w;
        } else {
            return d.v < v;
        }
    }
};

int main() {
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<Data> d;
    int X[M];
    ll W, V;
    for (int i = 0; i < N; i++) {
        cin >> W >> V;
        d.push_back(Data(W, V));
    }
    for (int i = 0; i < M; i++) {
        cin >> X[i];
    }
    int L, R;
    sort(d.begin(), d.end());
    // for (Data i : d) {
    //     cout << i.v << " " << i.w << "\n";
    // }
    for (int i = 0; i < Q; i++) {
        cin >> L >> R;
        ll ans = 0;
        L--;
        R--;
        bool flag[M] = {};
        for (int j = 0; j < N; j++) {
            int id = -1;
            for (int k = 0; k < M; k++) {
                if (L <= k && k <= R) continue;
                if (!flag[k] && d[j].w <= X[k]) {
                    if (id == -1) {
                        id = k;
                    } else if (X[k] < X[id]) {
                        id = k;
                    }
                }
            }
            if (id != -1) {
                ans += d[j].v;
                flag[id] = true;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}