結果

問題 No.2686 商品券の使い道
コンテスト
ユーザー AngrySadEight
提出日時 2025-12-16 01:13:58
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 145 ms / 3,000 ms
コード長 1,250 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 754 ms
コンパイル使用メモリ 74,520 KB
実行使用メモリ 36,036 KB
最終ジャッジ日時 2025-12-16 01:14:04
合計ジャッジ時間 6,116 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

vector<ll> fzt(vector<ll> &vec, ll N){
    vector<ll> ret(1 << N);
    for (ll i = 0; i < (1 << N); i++){
        ret[i] = vec[i];
    }
    for (ll i = 0; i < N; i++){
        for (ll j = 0; j < (1 << N); j++){
            if (!((j >> i) & 1)){
                ret[j + (1 << i)] = max(ret[j + (1 << i)], ret[j]);
            }
        }
    }
    return ret;
}

int main(){
    ll N, M, Q;
    cin >> N >> M >> Q;
    vector<ll> A(N);
    vector<ll> B(N);
    for (ll i = 0; i < N; i++){
        cin >> A[i] >> B[i];
    }
    vector<ll> sprice(1 << N, 0);
    vector<ll> sval(1 << N, 0);
    for (ll i = 0; i < (1 << N); i++){
        for (ll j = 0; j < N; j++){
            if ((i >> j) & 1){
                sprice[i] += A[j];
                sval[i] += B[j];
            }
        }
    }

    vector<ll> vec(1 << N, 0);
    for (ll i = 0; i < (1 << N); i++){
        if (sprice[i] <= Q){
            vec[i] = sval[i];
        }
    }
    vector<ll> vecmax = fzt(vec, N);
    ll ans = 0;
    for (ll i = 0; i < (1 << N); i++){
        if (sprice[i] <= M){
            ans = max(ans, sval[i] + vecmax[(1 << N) - 1 - i]);
        }
    }
    cout << ans << endl;
}
0