結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
|
提出日時 | 2024-11-08 21:49:11 |
言語 | C# (.NET 8.0.404) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,182 bytes |
コンパイル時間 | 12,237 ms |
コンパイル使用メモリ | 166,064 KB |
実行使用メモリ | 143,360 KB |
最終ジャッジ日時 | 2024-11-08 21:49:44 |
合計ジャッジ時間 | 31,718 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 TLE * 7 -- * 11 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (97 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
namespace AtCoder;#nullable enableusing System.Numerics;static class Extensions{public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray();public static int ToFlag(this int i){if (i < 0 || 31 <= i) throw new IndexOutOfRangeException();return 1 << i;}public static bool OfFlag(this int value, int i) => (value & ToFlag(i)) > 0;public static int WithFlag(this int value, int i, bool f) => f ? (value | ToFlag(i)) : (value & ~ToFlag(i));}class AtCoder{object? Solve(){var n = Int();var k = Int();var pz = new List<Complex>() { new(0, 0) };for (var i = 0; i < n; i++) pz.Add(new(Int(), Int()));var dz = new double[n + 1, n + 1];for (var i = 0; i <= n; i++) for (var j = 0; j <= n; j++) dz[i, j] = (pz[i] - pz[j]).Magnitude;var b = (n + 1).ToFlag();var dp = new double[b, n + 1, k + 1];for (var i = 0; i < b; i++) for (var j = 0; j <= n; j++) for (var l = 0; l <= k; l++) dp[i, j, l] = double.MaxValue;dp[1, 0, k] = 0;var q = new PriorityQueue<(double, int, int, int), double>();q.Enqueue((0, 1, 0, k), 0);while (q.Count > 0){var (ct, h, c, l) = q.Dequeue();if (ct > dp[h, c, l]) continue;for (var next = 0; next <= n; next++){var nt = ct + dz[c, next];if (next == 0){if (l == k || dp[h, 0, k] <= nt) continue;dp[h, 0, k] = nt;q.Enqueue((nt, h, 0, k), nt);continue;}if (l == 0) break;var nh = h.WithFlag(next, true);if (dp[nh, next, l - 1] <= nt) continue;dp[nh, next, l - 1] = nt;q.Enqueue((nt, nh, next, l - 1), nt);}}var ans = dp[b - 1, 0, k];return ans;}public static void Main() => new AtCoder().Run();public void Run(){var res = Solve();if (res != null){if (res is bool yes) res = yes ? "Yes" : "No";sw.WriteLine(res);}sw.Flush();}string[] input = Array.Empty<string>();int iter = 0;readonly StreamWriter sw = new(Console.OpenStandardOutput()) { AutoFlush = false };string String(){while (iter >= input.Length) (input, iter) = (Console.ReadLine()!.Trim().Split(' '), 0);return input[iter++];}T Input<T>() where T : IParsable<T> => T.Parse(String(), null);int Int() => Input<int>();void Out(object? x, string? separator = null){separator ??= Environment.NewLine;if (x is System.Collections.IEnumerable obj and not string){var firstLine = true;foreach (var item in obj){if (!firstLine) sw.Write(separator);firstLine = false;sw.Write(item);}}else sw.Write(x);sw.WriteLine();}}