結果
問題 | No.2375 watasou and hibit's baseball |
ユーザー |
|
提出日時 | 2023-07-07 22:34:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,386 ms / 2,000 ms |
コード長 | 830 bytes |
コンパイル時間 | 452 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 180,940 KB |
最終ジャッジ日時 | 2024-07-21 18:46:59 |
合計ジャッジ時間 | 12,004 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
N, A, B = map(int, input().split()) XYK = [tuple(map(int, input().split())) for i in range(N)] dp = {(1 << i, -1, i)for i in range(N)} # print(dp) for k in range(1, N): dp_ = set() for b, s, t in dp: for j in range(N): if (1 << j) & b > 0: continue if abs(XYK[t][2]-XYK[j][2]) >= B: dp_.add(((1 << j) | b, t, j)) continue if abs(XYK[j][0]-XYK[t][0])+abs(XYK[j][1]-XYK[t][1]) >= A: dp_.add(((1 << j) | b, t, j)) continue if s != -1 and abs(XYK[j][0]-XYK[t][0])+abs(XYK[j][1]-XYK[t][1])+abs(XYK[j][0]-XYK[s][0])+abs(XYK[j][1]-XYK[s][1]) >= A: dp_.add(((1 << j) | b, t, j)) dp = dp_ # print(dp) if dp: continue print(k) break else: print(N)