結果

問題 No.2686 商品券の使い道
コンテスト
ユーザー 👑 SPD_9X2
提出日時 2024-02-29 13:15:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,426 bytes
コンパイル時間 1,500 ms
コンパイル使用メモリ 168,864 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-09-30 05:05:29
合計ジャッジ時間 8,400 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 TLE * 1 -- * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

#define rep(i,n,m) for(ll (i)=(n);(i)<(m);(i)++)
#define rrep(i,n,m) for(ll (i)=(n);(i)>(m);(i)--)

/*想定TLE解 O(3^N)*/

int main(){

    ll N,M,Q;
    cin >> N >> M >> Q;

    vector<ll> A(N);
    vector<ll> B(N);
    
    rep(i,0,N){
        cin >> A[i] >> B[i];
    }

    // 完全下位互換を捨てる
    /*
    {
        vector<ll> newA,newB;
        rep(i,0,N){
            bool flag = true;
            rep(j,0,N){
                if (A[i] > A[j] && B[i] < B[j]){
                    flag = false;
                }
            }
            if (flag){
                newA.push_back(A[i]);
                newB.push_back(B[i]);
            }
        }
        A = newA;
        B = newB;
        N = newA.size();
    }
    */

    ll lps = 1;
    rep(i,0,N) lps *= 3;
    ll ans = 0;

    rep(bits,0,lps){

        ll bits_cp = bits;
        ll cost1 = 0;
        ll cost2 = 0;
        ll price = 0;

        rep(i,0,N){
            if (bits_cp % 3 == 0){
                cost1 += A[i];
                price += B[i];
            }else if (bits_cp % 3 == 1){
                cost2 += A[i];
                price += B[i];
            }
            bits_cp /= 3;
            if (cost1 > M || cost2 > Q) break;
        }

        if (cost1 <= M && cost2 <= Q){
            ans = max(ans , price);
        }

    }

    cout << ans << endl;

}
0