結果
問題 | No.2364 Knapsack Problem |
ユーザー | lanegue |
提出日時 | 2023-06-30 22:17:50 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 3 ms / 3,000 ms |
コード長 | 920 bytes |
コンパイル時間 | 5,704 ms |
コンパイル使用メモリ | 178,176 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-07 10:07:06 |
合計ジャッジ時間 | 6,517 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
import std; void main(){ auto input = readln.split.to!(int[]); auto N = input[0]; auto M = input[1]; auto W = input[2]; int[] w = readln.split.to!(int[]); int[] v = readln.split.to!(int[]); w ~= readln.split.to!(int[]).map!(a => -a).array; v ~= readln.split.to!(int[]).map!(a => -a).array; auto pat = new bool[(2 ^^ (N + M))]; pat[0] = true; auto q = DList!int(0); auto result = 0; while(!q.empty){ auto n = q.front; q.removeFront; auto a = 0; auto b = 0; for(auto i = 0; i < N + M; i++){ if(((n >> i) & 1) == 0) continue; a += v[i]; b += w[i]; } if(a > result){ result = a; } for(auto i = 0; i < N + M; i++){ if(((n >> i) & 1) == 1) continue; if(b + w[i] < 0 || b + w[i] > W) continue; if(pat[n | (1 << i)]) continue; pat[n | (1 << i)] = true; q.insertBack(n | (1 << i)); } } result.writeln; }