結果

問題 No.2375 watasou and hibit's baseball
ユーザー lam6er
提出日時 2025-04-15 23:18:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,815 ms / 2,000 ms
コード長 2,782 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 81,776 KB
実行使用メモリ 234,184 KB
最終ジャッジ日時 2025-04-15 23:20:19
合計ジャッジ時間 10,155 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    A = int(input[idx])
    idx += 1
    B = int(input[idx])
    idx += 1

    X = []
    Y = []
    K = []
    for _ in range(N):
        x = int(input[idx])
        y = int(input[idx + 1])
        k = int(input[idx + 2])
        X.append(x)
        Y.append(y)
        K.append(k)
        idx += 3

    # Precompute distances and K differences
    dist = [[0] * N for _ in range(N)]
    k_diff = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            dist[i][j] = abs(X[i] - X[j]) + abs(Y[i] - Y[j])
            k_diff[i][j] = abs(K[i] - K[j])

    # Initialize DP
    dp_by_size = [{} for _ in range(N + 2)]  # dp_by_size[m] holds states with mask size m
    for i in range(N):
        mask = 1 << i
        state = (mask, -1, i)
        dp_by_size[1][state] = 1

    max_length = 1

    for m in range(1, N):
        current_dp = dp_by_size[m]
        if not current_dp:
            continue
        for state in current_dp:
            current_mask, a_prev, b_prev = state
            current_length = current_dp[state]
            for c in range(N):
                if (current_mask & (1 << c)) != 0:
                    continue
                new_mask = current_mask | (1 << c)
                new_length = current_length + 1
                if a_prev == -1:
                    # j = 2
                    cond2 = (dist[b_prev][c] >= A)
                    cond3 = (k_diff[b_prev][c] >= B)
                    if cond2 or cond3:
                        new_a = b_prev
                        new_b = c
                        new_state = (new_mask, new_a, new_b)
                        if new_state not in dp_by_size[m + 1] or dp_by_size[m + 1].get(new_state, 0) < new_length:
                            dp_by_size[m + 1][new_state] = new_length
                            if new_length > max_length:
                                max_length = new_length
                else:
                    # j >= 3
                    cond2 = (dist[b_prev][c] >= A)
                    cond3 = (k_diff[b_prev][c] >= B)
                    cond4 = (dist[a_prev][c] + dist[b_prev][c] >= A)
                    if cond2 or cond3 or cond4:
                        new_a = b_prev
                        new_b = c
                        new_state = (new_mask, new_a, new_b)
                        if new_state not in dp_by_size[m + 1] or dp_by_size[m + 1].get(new_state, 0) < new_length:
                            dp_by_size[m + 1][new_state] = new_length
                            if new_length > max_length:
                                max_length = new_length

    print(max_length)

if __name__ == '__main__':
    main()
0