結果
問題 |
No.2389 Cheating Code Golf
|
ユーザー |
|
提出日時 | 2023-07-21 23:17:13 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 90 ms / 2,000 ms |
コード長 | 1,913 bytes |
コンパイル時間 | 3,695 ms |
コンパイル使用メモリ | 107,776 KB |
実行使用メモリ | 22,144 KB |
最終ジャッジ日時 | 2024-09-22 00:46:35 |
合計ジャッジ時間 | 7,395 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray(); public static void Main() { Solve(); } static void Solve() { var c = NList; var (n, m) = (c[0], c[1]); var map = NArr(n); var bitmax = 1 << n; var dp = new double[bitmax][]; for (var i = 0; i < dp.Length; ++i) dp[i] = Enumerable.Repeat(double.MinValue, m + 1).ToArray(); dp[0][0] = 0; var visited = new bool[bitmax][]; for (var i = 0; i < visited.Length; ++i) visited[i] = new bool[m + 1]; DFS(n, bitmax, 0, 0, map, dp, visited); WriteLine(dp[0][0]); } static void DFS(int n, int bitmax, int b, int mi, int[][] map, double[][] dp, bool[][] visited) { if (visited[b][mi]) return; var max = 0.0; for (var i = 0; i < n; ++i) { if ((b & (1 << i)) != 0) continue; var nb = b | (1 << i); DFS(n, bitmax, nb, mi, map, dp, visited); max = Math.Max(max, dp[nb][mi] + 1.0 / map[i][0]); if (mi + 1 < dp[i].Length) { DFS(n, bitmax, b, mi + 1, map, dp, visited); max = Math.Max(max, (1.0 / map[i][2]) * (dp[nb][mi] + 1.0 / map[i][1]) + (1.0 - 1.0 / map[i][2]) * dp[b][mi + 1]); } } visited[b][mi] = true; dp[b][mi] = max; } static void DebugTable<T>(T[][] table) { Console.WriteLine("{"); foreach (var list in table) Console.WriteLine(string.Join(", ", list)); Console.WriteLine("}"); } }