結果
問題 | No.2730 Two Types Luggage |
ユーザー |
![]() |
提出日時 | 2024-04-20 17:51:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 687 ms / 2,000 ms |
コード長 | 1,016 bytes |
コンパイル時間 | 909 ms |
コンパイル使用メモリ | 83,408 KB |
最終ジャッジ日時 | 2025-02-21 07:07:34 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>int main(){int n, m;long long w;std::cin>>n>>m>>w;std::vector<int> a(n);std::vector<int> b(m);std::vector<int> c(m);for(int i = 0; i < n; i++){std::cin>>a[i];}for(int i = 0; i < m; i++){std::cin>>b[i];}for(int i = 0; i < m; i++){std::cin>>c[i];}std::sort(a.rbegin(), a.rend());std::vector<long long> sum(n+1);for(int i = 0; i < n; i++){sum[i+1] = sum[i] + a[i];}// タイプYを選ぶ全パターン列挙typedef struct {long long weight;long long cost;} knapsack_t;std::vector<knapsack_t> patterns;for(int bit = 0; bit < (1<<m); bit++){knapsack_t knapsack = {};for(int i = 0; i < m; i++) if(bit>>i&1){knapsack.weight += b[i];knapsack.cost += c[i];}patterns.push_back(knapsack);}long long ans = 0;for(auto p: patterns) if(p.weight <= w){int remain = std::min(w-p.weight, (long long)n);ans = std::max(ans, p.cost + sum[remain]);}std::cout << ans << std::endl;}