結果
問題 | No.2730 Two Types Luggage |
ユーザー |
|
提出日時 | 2024-04-19 22:01:58 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 562 ms / 2,000 ms |
コード長 | 1,074 bytes |
コンパイル時間 | 2,929 ms |
コンパイル使用メモリ | 252,192 KB |
実行使用メモリ | 18,848 KB |
最終ジャッジ日時 | 2024-10-11 15:11:13 |
合計ジャッジ時間 | 14,544 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include<bits/stdc++.h>using namespace std;const int INF = 1<<30;const int MOD = 998244353;//const long long INF = 1LL<<60;using graph = vector<vector<int>>;using ll = long long;int main(){ll n, m, w;cin >> n >> m >> w;vector<ll> a(n), b(m), c(m);for (int i=0; i < n; i++) cin >> a[i];for (int i=0; i < m; i++) cin >> b[i];for (int i=0; i < m; i++) cin >> c[i];sort(a.begin(), a.end(), greater<ll>());vector<ll> acc_a(n+1);for (int i=1; i < n+1; i++) acc_a[i] = acc_a[i-1] + a[i-1];ll ans = 0LL;for (int i=0; i < (1<<m); i++){ll weight = 0;ll value = 0;bool flag = true;for (int j=0; j < m; j++){if (i & (1<<j)){weight += b[j];value += c[j];}if (weight > w){flag = false;break;}}if (flag){ll rem = w - weight;ans = max(ans, value + acc_a[min(n, rem)]);}}cout << ans << endl;}