結果
問題 | No.2375 watasou and hibit's baseball |
ユーザー |
|
提出日時 | 2023-06-21 16:34:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 900 ms / 2,000 ms |
コード長 | 1,018 bytes |
コンパイル時間 | 956 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 123,136 KB |
最終ジャッジ日時 | 2024-07-08 08:44:52 |
合計ジャッジ時間 | 11,644 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
import sys def d(i, j): return abs(X[i] - X[j]) + abs(Y[i] - Y[j]) N, A, B = map(int, sys.stdin.readline().split()) X, Y, K = [], [], [] for _ in range(N): x, y, k = map(int, sys.stdin.readline().split()) X.append(x) Y.append(y) K.append(k) dp = [[[0] * N for _ in range(N)] for _ in range(1 << N)] for i in range(N): for j in range(N): if i != j: dp[(1 << i) | (1 << j)][i][j] = int(d(i, j) >= A or abs(K[i] - K[j]) >= B) for bit in range(1 << N): for i in range(N): for j in range(N): if dp[bit][i][j] and bit == (bit | (1 << i)) and bit == (bit | (1 << j)): for k in range(N): if not bit & (1 << k): if d(k, i) + d(k, j) >= A or abs(K[i] - K[k]) >= B: dp[bit | (1 << k)][k][i] = 1 ans = 1 for i in range(1 << N): for j in range(N): for k in range(N): if dp[i][j][k]: ans = max(ans, bin(i).count("1")) print(ans)