結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    N, A, B = map(int, sys.stdin.readline().split())
    balls = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
    X = [x for x, y, k in balls]
    Y = [y for x, y, k in balls]
    K = [k for x, y, k in balls]
    
    # Precompute distance 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: mask -> {(a_prev, b_prev): max_length}
    dp = defaultdict(dict)
    max_len = 1
    for i in range(N):
        mask = 1 << i
        a_prev = -1
        b_prev = i
        dp[mask][(a_prev, b_prev)] = 1
    
    # Process masks in order of increasing size
    for m in range(1, N + 1):
        # Get all masks with exactly m bits set
        masks = [mask for mask in dp if bin(mask).count('1') == m]
        for mask in masks:
            # Process each (a_prev, b_prev) pair in the current mask
            pairs = list(dp[mask].items())
            for (a_prev, b_prev), current_len in pairs:
                # Try adding each possible next ball
                for next_ball in range(N):
                    if mask & (1 << next_ball):
                        continue  # already used
                    new_mask = mask | (1 << next_ball)
                    new_a = b_prev
                    new_b = next_ball
                    j = current_len + 1
                    
                    # Check conditions based on j
                    if j == 2:
                        # Check condition 2 or 3
                        cond2 = dist[b_prev][next_ball] >= A
                        cond3 = k_diff[b_prev][next_ball] >= B
                        if cond2 or cond3:
                            new_len = j
                            key = (new_a, new_b)
                            if key not in dp[new_mask] or dp[new_mask].get(key, 0) < new_len:
                                dp[new_mask][key] = new_len
                                if new_len > max_len:
                                    max_len = new_len
                    else:
                        # j >=3, check condition 3 or 4
                        cond3 = k_diff[b_prev][next_ball] >= B
                        sum_dist = dist[a_prev][next_ball] + dist[b_prev][next_ball]
                        cond4 = sum_dist >= A
                        if cond3 or cond4:
                            new_len = j
                            key = (new_a, new_b)
                            if key not in dp[new_mask] or dp[new_mask].get(key, 0) < new_len:
                                dp[new_mask][key] = new_len
                                if new_len > max_len:
                                    max_len = new_len
    print(max_len)

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