結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
![]() |
提出日時 | 2022-04-01 21:51:12 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 8 ms / 5,000 ms |
コード長 | 1,673 bytes |
コンパイル時間 | 1,415 ms |
コンパイル使用メモリ | 143,968 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-22 14:45:43 |
合計ジャッジ時間 | 2,025 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
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, M;readf("%s %s\n", &N, &M);auto scores = new long[][](N + 1, N + 1);foreach (i; 0 .. M) {int u, v;long scr;readf("%s %s %s\n", &u, &v, &scr);u++;v++;scores[u][v] = scr;}auto dp = new long[](1 << N);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 += scores[u][v];}chmax(dp[s | (1 << (v - 1))], dp[s] + tot);}long ret = dp[(1 << N) - 1];writeln(ret);}