結果
問題 | No.286 Modulo Discount Store |
ユーザー |
![]() |
提出日時 | 2022-04-01 21:58:48 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 1,655 bytes |
コンパイル時間 | 1,278 ms |
コンパイル使用メモリ | 141,884 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-22 14:45:54 |
合計ジャッジ時間 | 2,526 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
import std.stdio, std.string, std.conv; import std.algorithm, std.math; import std.range; import std.container.rbtree, std.container.dlist; import std.container.binaryheap, std.container.array; import std.typecons; alias mstring = char[]; const long INF = 1L << 60L; const long mod = 1_000_000_000 + 7; void chmin(T)(ref T x, T y) { x = min(x, y); } void chmax(T)(ref T x, T y) { x = max(x, y); } // 単一の数値を取得 // readln.chomp.to!int; // or // int a; // readf("%s\n", a); // 複数の数値を取得(可変数個の場合推奨) // readln.chomp.split.map!(to!long).array // 複数の数値を取得(固定数個の場合、推奨) // int a, b; // readf("%s %s\n", &a, &b); // インデントを一個ずらして複数の数値を取得(累積和とかで1-indexedの方が良い時がある) // long[] vs = readln.chomp.split.map!(to!long).array; // vs = [0L] ~ vs; // 小数点は以下で指定 // double ret = 10.0; // writefln("%.12f", ret); // 配列の最後の要素は arr[$-1] でアクセスできる void main() { int N = readln.chomp.to!int; auto cst = new long[](N + 1); foreach (i; 1 .. N + 1) readf("%s\n", &(cst[i])); auto dp = new long[](1 << N); foreach (s; 0 .. (1 << N)) dp[s] = INF; dp[0] = 0L; foreach (s; 0 .. (1 << N)) foreach (v; 1 .. N + 1) { if (s & (1 << (v - 1))) continue; long tot = 0L; foreach (u; 1 .. N + 1) { if ((s & (1 << (u - 1))) == 0) continue; tot += cst[u]; } chmin(dp[s | (1 << (v - 1))], dp[s] + max(0L, cst[v] - (tot % 1_000L))); } long ret = dp[(1 << N) - 1]; writeln(ret); }