結果
問題 | No.2375 watasou and hibit's baseball |
ユーザー |
![]() |
提出日時 | 2023-07-07 22:38:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 743 ms / 2,000 ms |
コード長 | 1,524 bytes |
コンパイル時間 | 151 ms |
コンパイル使用メモリ | 82,716 KB |
実行使用メモリ | 105,884 KB |
最終ジャッジ日時 | 2024-07-21 18:51:51 |
合計ジャッジ時間 | 16,134 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
def popcount(n): cnt = 0 while n: cnt += n & 1 n //= 2 return cnt N, A, B = map(int, input().split()) X, Y, K = [0] * N, [0] * N, [0] * N for i in range(N): X[i], Y[i], K[i] = map(int, input().split()) N2 = 1 << N dp = [0] * N*N*N2 def f(s, a, b): return s * N ** 2 + a * N + b def dist(a, b): return abs(X[a] - X[b]) + abs(Y[a] - Y[b]) def check2(a, b): if A <= dist(a, b): return True if B <= abs(K[a] - K[b]): return True return False def check3(a, b, c): if B <= abs(K[a] - K[b]): return True if A <= dist(a, b) + dist(a, c): return True return False for s in range(1, N2): p = popcount(s) for i in range(N): if (s >> i) & 1: continue if p == 1: for j in range(N): if (s >> j) & 1 == 0: continue if check2(i, j): dp[f(s|(1 << i),i,j)] = 1 else: for j in range(N): if (s >> j) & 1 == 0: continue for k in range(N): if k == i or k == j or (s >> k) & 1 == 0: continue if check3(i, j, k): dp[f(s|(1 << i),i,j)] |= dp[f(s,j,k)] ans = 1 for s in range(1, N2): for i in range(N): for j in range(N): if dp[f(s,i,j)]: ans = max(ans, popcount(s)) print(ans)