結果

問題 No.2375 watasou and hibit's baseball
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:29:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,658 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 82,596 KB
実行使用メモリ 276,152 KB
最終ジャッジ日時 2025-03-31 17:30:38
合計ジャッジ時間 5,457 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    n, A, B = map(int, sys.stdin.readline().split())
    balls = []
    for _ in range(n):
        x, y, k = map(int, sys.stdin.readline().split())
        balls.append((x, y, k))
    
    # Precompute distance and K differences between all pairs
    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(balls[i][0] - balls[j][0]) + abs(balls[i][1] - balls[j][1])
            K_diff[i][j] = abs(balls[i][2] - balls[j][2])
    
    # DP dictionary: key=(mask, a_prev, b_prev), value=length
    dp = dict()
    queue = deque()
    for i in range(n):
        mask = 1 << i
        key = (mask, -1, i)
        dp[key] = 1
        queue.append(key)
    
    max_len = 1  # At least one ball is thrown
    
    visited = set()
    while queue:
        key = queue.popleft()
        if key in visited:
            continue
        visited.add(key)
        mask, a_prev, b_prev = key
        current_len = dp[key]
        m = bin(mask).count('1')
        
        for k in range(n):
            if (mask & (1 << k)) == 0:
                new_mask = mask | (1 << k)
                new_m = m + 1
                j = new_m
                
                condition_met = False
                
                if j == 2:
                    # Check j=2: previous is b_prev (single element)
                    d = dist[b_prev][k]
                    kd = K_diff[b_prev][k]
                    if d >= A or kd >= B:
                        condition_met = True
                else:
                    if j >= 3:
                        # Check j >=3
                        kd = K_diff[b_prev][k]
                        if kd >= B:
                            condition_met = True
                        else:
                            # Check sum of distances to previous two
                            d1 = dist[k][b_prev]
                            d2 = dist[k][a_prev]
                            if (d1 + d2) >= A:
                                condition_met = True
                
                if condition_met:
                    new_a = b_prev
                    new_b = k
                    new_key = (new_mask, new_a, new_b)
                    if new_key not in dp or dp[new_key] < new_m:
                        dp[new_key] = new_m
                        if new_m > max_len:
                            max_len = new_m
                        if new_key not in visited:
                            queue.append(new_key)
    
    print(max_len)

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