結果
問題 | No.286 Modulo Discount Store |
ユーザー |
|
提出日時 | 2017-06-08 13:08:25 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 1,038 bytes |
コンパイル時間 | 750 ms |
コンパイル使用メモリ | 100,096 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-12 19:48:18 |
合計ジャッジ時間 | 2,168 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
import std.algorithm, std.conv, std.range, std.stdio, std.string; void main() { auto n = readln.chomp.to!size_t; auto mi = n.iota.map!(_ => readln.chomp.to!int).array; auto si = new int[](1 << n), pi = new int[](1 << n); pi[1..$] = int.max; foreach (i; 1..(1 << n)) { auto j = i.bsf; si[i] = si[i.bitComp(j)] + mi[j]; } foreach (i; 1..(1 << n)) foreach (j; 0..n) if (i.bitTest(j)) { auto k = i.bitComp(j); pi[i] = min(pi[i], pi[k] + max(mi[j] - si[k] % 1000, 0)); } writeln(pi[$-1]); } pragma(inline) { pure bool bitTest(T)(T n, size_t i) { return (n & (T(1) << i)) != 0; } pure T bitSet(T)(T n, size_t i) { return n | (T(1) << i); } pure T bitReset(T)(T n, size_t i) { return n & ~(T(1) << i); } pure T bitComp(T)(T n, size_t i) { return n ^ (T(1) << i); } import core.bitop; pure int bsf(T)(T n) { return core.bitop.bsf(ulong(n)); } pure int bsr(T)(T n) { return core.bitop.bsr(ulong(n)); } pure int popcnt(T)(T n) { return core.bitop.popcnt(ulong(n)); } }