結果
問題 | No.2375 watasou and hibit's baseball |
ユーザー |
👑 |
提出日時 | 2023-07-07 21:42:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,009 ms / 2,000 ms |
コード長 | 1,474 bytes |
コンパイル時間 | 455 ms |
コンパイル使用メモリ | 82,496 KB |
実行使用メモリ | 106,144 KB |
最終ジャッジ日時 | 2024-07-21 17:30:23 |
合計ジャッジ時間 | 19,862 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
def popcount(x):x = x - ((x >> 1) & 0x55555555)x = (x & 0x33333333) + ((x >> 2) & 0x33333333)x = (x + (x >> 4)) & 0x0F0F0F0Fx += x >> 8x += x >> 16return x & 0x0000003Fn, a, b = map(int, input().split())X = [0] * nY = [0] * nK = [0] * nfor i in range(n):X[i], Y[i], K[i] = map(int, input().split())def f(bit, i, j):return (bit * n + i) * n + jdp = [False] * ((1 << n) * n * n)for i in range(n):dp[f(1 << i, i, i)] = Truedef dist(i, j):return abs(X[i] - X[j]) + abs(Y[i] - Y[j])for bit in range(1 << n):ind = []for i in range(n):if bit >> i & 1:ind.append(i)for i in ind:for j in ind:if i == j:continueif len(ind) == 2 and a <= dist(i, j):dp[f(bit, i, j)] |= dp[f(bit ^ (1 << j), i, i)]if b <= abs(K[i] - K[j]):dp[f(bit, i, j)] |= dp[f(bit ^ (1 << j), i, i)]for k in ind:if k == i or k == j:continueif a <= dist(i, k) + dist(j, k):dp[f(bit, j, k)] |= dp[f(bit ^ (1 << k), i, j)]if b <= abs(K[j] - K[k]):dp[f(bit, j, k)] |= dp[f(bit ^ (1 << k), i, j)]ans = 0for bit in range(1 << n):pc = popcount(bit)for i in range(n):for j in range(n):if dp[f(bit, i, j)]:ans = max(ans, pc)print(ans)