結果
問題 | No.2375 watasou and hibit's baseball |
ユーザー |
|
提出日時 | 2023-07-07 22:39:12 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,133 ms / 2,000 ms |
コード長 | 2,319 bytes |
コンパイル時間 | 4,956 ms |
コンパイル使用メモリ | 107,392 KB |
実行使用メモリ | 35,584 KB |
最終ジャッジ日時 | 2024-07-21 18:53:42 |
合計ジャッジ時間 | 22,695 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
コンパイルメッセージ
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, a, b) = (c[0], c[1], c[2]);var map = NArr(n);var bitmax = 1 << n;var infarr = Enumerable.Repeat(int.MinValue, n * n).ToArray();var dp = new int[bitmax][];for (var i = 0; i < dp.Length; ++i) dp[i] = (int[]) infarr.Clone();dp[0][0] = 0;for (var bit = 0; bit < bitmax; ++bit){var pc = PopCount(bit);for (var i = 0; i < dp[bit].Length; ++i){var p1 = i % n;var p2 = i / n;if ((pc == 1 && (bit & (1 << p1)) == 0)|| (pc == 2 && ((bit & (1 << p1)) == 0 || (bit & (1 << p2)) == 0))) continue;for (var next = 0; next < n; ++next){if ((bit & (1 << next)) != 0) continue;if (pc == 0|| (pc == 1 && a <= Dist(map, p1, next))|| (pc >= 1 && b <= Speed(map, p1, next))|| (pc >= 2 && a <= Dist(map, p1, next) + Dist(map, p2, next))){dp[bit | (1 << next)][p1 * n + next] = Math.Max(dp[bit | (1 << next)][p1 * n + next], dp[bit][i] + 1);}}}}var ans = 0;foreach (var di in dp) ans = Math.Max(ans, di.Max());WriteLine(ans);}static int Dist(int[][] map, int i, int j){return Math.Abs(map[i][0] - map[j][0]) + Math.Abs(map[i][1] - map[j][1]);}static int Speed(int[][] map, int i, int j){return Math.Abs(map[i][2] - map[j][2]);}static int PopCount(int n){var ans = 0;while (n > 0){ans += n % 2;n >>= 1;}return ans;}}