提出 #62063724

---

ソースコード 拡げる

#include<bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int n, w;
    cin >> n >> w;
    array<vector<int>, 3> f;
    for(int i = 0; i < 3; i++) {
        f[i].resize(w + 1, 0);
    }
    for(int i = 0, v, a, c; i < n; i++) {
        cin >> v >> a >> c;
        v--;
        for(int j = w; j >= c; j--) {
            f[v][j] = max(f[v][j - c] + a, f[v][j]);
        }
    }
    cerr << "OK\n";

    auto check = [&](int x) -> bool {
        int res = 0;
        for(int i = 0; i < 3; i++) {
            int add = (int)(lower_bound(f[i].begin(), f[i].end(), x) - f[i].begin());
            if(add == w + 1) {
                return 0;
            }
            res += add;
        }
        return res <= w;
    };

    int lo = 0, hi = 1e9, ans = -1;
    while(lo <= hi) {
        int mid = (lo + hi) >> 1;
        if(check(mid)) {
            lo = mid + 1, ans = mid;
        } else {
            hi = mid - 1;
        }
    }

    cout << ans << '\n';

    return 0;
}

提出情報

ジャッジ結果