結果
問題 | No.2375 watasou and hibit's baseball |
ユーザー |
![]() |
提出日時 | 2023-07-07 21:57:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 859 ms / 2,000 ms |
コード長 | 1,460 bytes |
コンパイル時間 | 256 ms |
コンパイル使用メモリ | 82,504 KB |
実行使用メモリ | 109,428 KB |
最終ジャッジ日時 | 2024-07-21 17:52:40 |
合計ジャッジ時間 | 11,042 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
import sys input = sys.stdin.readline mod = 998244353 def dist(A, B): return abs(A[0] - B[0]) + abs(A[1] - B[1]) def dist2(A, B): return abs(A[2] - B[2]) N, A, B = map(int, input().split()) XYK = [] for _ in range(N): XYK.append(tuple(map(int, input().split()))) dp = [[[0] * (1 << N) for _ in range(N+1)] for _ in range(N + 1)] dp[N][N][0] = 1 for state in range(1 << N): for last1 in range(N + 1): for last2 in range(N + 1): if dp[last1][last2][state] == 0: continue for nxt in range(N): if state >> nxt & 1: continue new_state = state | (1 << nxt) ok = 0 if last1 == last2 == N: ok = 1 elif last2 == N: if dist(XYK[nxt], XYK[last1]) >= A or dist2(XYK[nxt], XYK[last1]) >= B: ok = 1 else: if dist(XYK[nxt], XYK[last1]) + dist(XYK[nxt], XYK[last2]) >= A or dist2(XYK[nxt], XYK[last1]) >= B: ok = 1 if ok: dp[nxt][last1][new_state] = 1 ans = 1 for last1 in range(N + 1): for last2 in range(N + 1): for state in range(1 << N): if dp[last1][last2][state]: tmp = 0 for j in range(N): tmp += state >> j & 1 ans = max(ans, tmp) print(ans)