結果
問題 |
No.2686 商品券の使い道
|
ユーザー |
![]() |
提出日時 | 2024-03-20 21:37:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 126 ms / 3,000 ms |
コード長 | 976 bytes |
コンパイル時間 | 2,179 ms |
コンパイル使用メモリ | 196,944 KB |
最終ジャッジ日時 | 2025-02-20 08:52:17 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int N, M, Q; cin >> N >> M >> Q; vector<int> A(N), B(N); for (int i = 0; i < N; i++){ cin >> A[i] >> B[i]; } vector<long long> sumA(1 << N, 0); vector<long long> sumB(1 << N, 0); for (int i = 0; i < (1 << N); i++){ for (int j = 0; j < N; j++){ if ((i >> j & 1) == 1){ sumA[i] += A[j]; sumB[i] += B[j]; } } } vector<long long> C(1 << N, 0); vector<long long> D(1 << N, 0); for (int i = 0; i < (1 << N); i++){ if (sumA[i] <= M){ C[i] = sumB[i]; } if (sumA[i] <= Q){ D[i] = sumB[i]; } } for (int i = 0; i < N; i++){ for (int j = 0; j < (1 << N); j++){ if ((j >> i & 1) == 1){ C[j] = max(C[j], C[j - (1 << i)]); D[j] = max(D[j], D[j - (1 << i)]); } } } long long ans = 0; for (int i = 0; i < (1 << N); i++){ ans = max(ans, C[i] + D[(1 << N) - 1 - i]); } cout << ans << endl; }