結果
問題 | No.2375 watasou and hibit's baseball |
ユーザー |
|
提出日時 | 2024-12-13 03:24:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 885 ms / 2,000 ms |
コード長 | 2,203 bytes |
コンパイル時間 | 2,536 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 124,336 KB |
最終ジャッジ日時 | 2024-12-13 03:25:08 |
合計ジャッジ時間 | 15,172 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
# https://yukicoder.me/problems/no/2375def dist(from_i, to_j, xyk):xi, yi, _ = xyk[from_i]xj, yj, _ = xyk[to_j]return abs(xi - xj) + abs(yi - yj)def diff_speed(from_i, to_j, xyk):_, _, ki = xyk[from_i]_, _, kj = xyk[to_j]return abs(ki - kj)def main():N, A, B = map(int, input().split())xyk = []for _ in range(N):x, y, k = map(int, input().split())xyk.append((x, y, k))bits = [[[False for _ in range(N)] for _ in range(N)] for _ in range(2 ** N)]# 2投目までfor i in range(N):for j in range(N):if i != j:if dist(i, j, xyk) >= A or diff_speed(i, j, xyk) >= B:bits[(1 << i) | (1 << j)][i][j] = Truebit_map = {}for bit in range(2 ** N):bit_count = 0for i in range(N):if bit & (1 << i) > 0:bit_count += 1if bit_count >= 2:if bit_count not in bit_map:bit_map[bit_count] = []bit_map[bit_count].append(bit)for bit_count in range(2, N):for bit in bit_map[bit_count]:for from_i in range(N):for from_j in range(N):if from_i == from_j:continuemask = (1 << from_i) & (1 << from_j)if bit & mask == mask and bits[bit][from_i][from_j]:for to_k in range(N):if bit & (1 << to_k) == 0:if diff_speed(from_j, to_k, xyk) >= B or (dist(from_i, to_k, xyk) + dist(from_j, to_k, xyk) >= A):new_bit = bit | (1 << to_k)bits[new_bit][from_j][to_k] = Trueanswer = 1for bit_count in range(2, N + 1):for bit in bit_map[bit_count]:is_ok = Falsefor i in range(N):for j in range(N):if bits[bit][i][j]:is_ok = Trueif is_ok:answer = max(answer, bit_count)print(answer)if __name__ == "__main__":main()