結果
| 問題 | No.2686 商品券の使い道 |
| ユーザー |
👑  SPD_9X2
|
| 提出日時 | 2024-02-29 13:15:42 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,426 bytes |
| コンパイル時間 | 1,481 ms |
| コンパイル使用メモリ | 169,568 KB |
| 実行使用メモリ | 10,004 KB |
| 最終ジャッジ日時 | 2024-03-19 00:36:36 |
| 合計ジャッジ時間 | 8,535 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,676 KB |
| testcase_01 | AC | 2 ms
6,676 KB |
| testcase_02 | AC | 2,612 ms
6,676 KB |
| testcase_03 | TLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| evil_random20_1.txt | -- | - |
| evil_random20_2.txt | -- | - |
| evil_random20_3.txt | -- | - |
ソースコード
#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;
}