結果
問題 | No.2375 watasou and hibit's baseball |
ユーザー | rlangevin |
提出日時 | 2023-07-07 22:38:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 806 ms / 2,000 ms |
コード長 | 1,524 bytes |
コンパイル時間 | 290 ms |
コンパイル使用メモリ | 87,216 KB |
実行使用メモリ | 107,740 KB |
最終ジャッジ日時 | 2023-09-29 00:09:59 |
合計ジャッジ時間 | 18,528 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,536 KB |
testcase_01 | AC | 75 ms
71,308 KB |
testcase_02 | AC | 75 ms
71,480 KB |
testcase_03 | AC | 522 ms
91,288 KB |
testcase_04 | AC | 127 ms
77,776 KB |
testcase_05 | AC | 93 ms
76,744 KB |
testcase_06 | AC | 704 ms
107,452 KB |
testcase_07 | AC | 76 ms
71,432 KB |
testcase_08 | AC | 400 ms
85,872 KB |
testcase_09 | AC | 75 ms
71,168 KB |
testcase_10 | AC | 78 ms
71,140 KB |
testcase_11 | AC | 289 ms
81,052 KB |
testcase_12 | AC | 781 ms
106,660 KB |
testcase_13 | AC | 550 ms
92,692 KB |
testcase_14 | AC | 77 ms
71,348 KB |
testcase_15 | AC | 465 ms
84,868 KB |
testcase_16 | AC | 230 ms
80,144 KB |
testcase_17 | AC | 694 ms
106,352 KB |
testcase_18 | AC | 77 ms
71,472 KB |
testcase_19 | AC | 75 ms
71,500 KB |
testcase_20 | AC | 351 ms
82,688 KB |
testcase_21 | AC | 652 ms
106,212 KB |
testcase_22 | AC | 74 ms
71,308 KB |
testcase_23 | AC | 656 ms
106,260 KB |
testcase_24 | AC | 659 ms
106,216 KB |
testcase_25 | AC | 76 ms
71,368 KB |
testcase_26 | AC | 667 ms
106,208 KB |
testcase_27 | AC | 715 ms
106,360 KB |
testcase_28 | AC | 618 ms
105,616 KB |
testcase_29 | AC | 571 ms
105,728 KB |
testcase_30 | AC | 791 ms
106,796 KB |
testcase_31 | AC | 775 ms
107,036 KB |
testcase_32 | AC | 766 ms
106,816 KB |
testcase_33 | AC | 757 ms
107,428 KB |
testcase_34 | AC | 626 ms
105,900 KB |
testcase_35 | AC | 613 ms
105,788 KB |
testcase_36 | AC | 561 ms
105,064 KB |
testcase_37 | AC | 806 ms
107,740 KB |
testcase_38 | AC | 368 ms
102,956 KB |
ソースコード
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)