結果

問題 No.2375 watasou and hibit's baseball
ユーザー lam6er
提出日時 2025-04-15 23:26:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 835 ms / 2,000 ms
コード長 2,976 bytes
コンパイル時間 213 ms
コンパイル使用メモリ 82,068 KB
実行使用メモリ 134,900 KB
最終ジャッジ日時 2025-04-15 23:28:32
合計ジャッジ時間 6,860 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    N, A, B = map(int, sys.stdin.readline().split())
    X = []
    Y = []
    K = []
    for _ in range(N):
        x, y, k = map(int, sys.stdin.readline().split())
        X.append(x)
        Y.append(y)
        K.append(k)
    
    # 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 -> {(prev, prev_prev): max_length}
    dp = defaultdict(dict)
    for i in range(N):
        mask = 1 << i
        dp[mask][(i, -1)] = 1
    
    max_len = 1
    
    current_bit_count = 1
    while current_bit_count <= N:
        # Get all masks with current_bit_count bits
        masks_to_process = []
        for mask in list(dp.keys()):
            if bin(mask).count('1') == current_bit_count:
                masks_to_process.append(mask)
        
        if not masks_to_process:
            current_bit_count += 1
            continue
        
        for mask in masks_to_process:
            states = dp[mask]
            for (prev, prev_prev), length in states.items():
                # Try adding each possible w not in mask
                for w in range(N):
                    if (mask & (1 << w)) != 0:
                        continue
                    # Check conditions
                    if prev_prev == -1:
                        # j=2
                        cond2 = (dist[prev][w] >= A)
                        cond3 = (k_diff[prev][w] >= B)
                        if cond2 or cond3:
                            new_mask = mask | (1 << w)
                            new_state = (w, prev)
                            new_length = length + 1
                            # Update dp
                            if new_state not in dp[new_mask] or dp[new_mask].get(new_state, 0) < new_length:
                                dp[new_mask][new_state] = new_length
                                if new_length > max_len:
                                    max_len = new_length
                    else:
                        # j >=3
                        cond3 = (k_diff[prev][w] >= B)
                        cond4 = (dist[prev][w] + dist[prev_prev][w] >= A)
                        if cond3 or cond4:
                            new_mask = mask | (1 << w)
                            new_state = (w, prev)
                            new_length = length + 1
                            if new_state not in dp[new_mask] or dp[new_mask].get(new_state, 0) < new_length:
                                dp[new_mask][new_state] = new_length
                                if new_length > max_len:
                                    max_len = new_length
        current_bit_count += 1
    
    print(max_len)

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