結果
問題 | No.2869 yuusaan's Knapsacks |
ユーザー | tottoripaper |
提出日時 | 2024-09-03 16:46:26 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 185 ms / 4,500 ms |
コード長 | 1,927 bytes |
コンパイル時間 | 2,470 ms |
コンパイル使用メモリ | 210,604 KB |
実行使用メモリ | 13,364 KB |
最終ジャッジ日時 | 2024-09-03 16:46:31 |
合計ジャッジ時間 | 5,175 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> using ll = std::int64_t; int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int N, M; std::cin >> N >> M; std::vector<int> e; e.resize(N); for(int i=0;i<N;i++){ std::cin >> e[i]; } std::vector<int> v, w; v.resize(M); w.resize(M); for(int i=0;i<M;i++){ std::cin >> v[i] >> w[i]; } std::vector<ll> sum_v(1 << M, 0), sum_w(1 << M, 0); for(int i=0;i<(1<<M);i++){ for(int j=0;j<M;j++){ if(i >> j & 1){ sum_v[i] += v[j]; sum_w[i] += w[j]; } } } std::vector dp(N + 1, std::vector<int>(1 << M, -1)); std::vector prev(N + 1, std::vector<int>(1 << M, -1)); dp[0][0] = 0; for(int i=0;i<N;i++){ for(int j=0;j<(1<<M);j++){ if(sum_w[j] > e[i]){ continue; } int cj = j ^ ((1 << M) - 1); int k = cj; while(true){ int nv = dp[i][k] + sum_v[j]; if(nv > dp[i + 1][j ^ k]){ dp[i + 1][j ^ k] = nv; prev[i + 1][j ^ k] = k; } if(k == 0){ break; } k = (k - 1) & cj; } } } int v_max = -1, j_max = -1; for(int j=0;j<(1<<M);j++){ if(v_max < dp[N][j]){ v_max = dp[N][j]; j_max = j; } } std::vector<int> used(N); for(int i=N;i>=1;i--){ used[i - 1] = j_max ^ prev[i][j_max]; j_max = prev[i][j_max]; } std::cout << v_max << std::endl; for(int i=0;i<N;i++){ std::cout << __builtin_popcount(used[i]); for(int j=0;j<M;j++){ if(used[i] >> j & 1){ std::cout << " " << (j + 1); } } std::cout << std::endl; } }