結果

問題 No.2375 watasou and hibit's baseball
ユーザー lam6er
提出日時 2025-03-20 18:49:50
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,871 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 106,856 KB
最終ジャッジ日時 2025-03-20 18:52:13
合計ジャッジ時間 5,398 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr +=1
    A = int(input[ptr])
    ptr +=1
    B = int(input[ptr])
    ptr +=1
    
    X = []
    Y = []
    K = []
    for _ in range(n):
        x = int(input[ptr])
        ptr +=1
        y = int(input[ptr])
        ptr +=1
        k = int(input[ptr])
        ptr +=1
        X.append(x)
        Y.append(y)
        K.append(k)
    
    max_len = 1
    INF = (1 << n)
    # Initialize DP: dp[mask][prev1][prev2_idx]
    dp = [ [ [-1 for _ in range(n+1)] for __ in range(n)] for ___ in range(1<<n)]
    from collections import deque
    queue = deque()
    
    for i in range(n):
        mask = 1 << i
        prev1 = i
        prev2_idx = n  # indicates no previous ball
        dp[mask][prev1][prev2_idx] = 1
        queue.append( (mask, prev1, prev2_idx) )
        max_len = 1
    
    while queue:
        mask, prev1, prev2_idx = queue.popleft()
        current_len = dp[mask][prev1][prev2_idx]
        if current_len == -1:
            continue  # invalid state
        # Try to add each possible next ball
        for next_ball in range(n):
            if not (mask & (1 << next_ball)):
                new_mask = mask | (1 << next_ball)
                m = bin(mask).count('1')
                j = m +1  # j is the position of next_ball in the new sequence
                
                # Calculate distances and differences
                dist_prev1_next = abs(X[prev1] - X[next_ball]) + abs(Y[prev1] - Y[next_ball])
                diff_k_prev1_next = abs(K[prev1] - K[next_ball])
                cond = False
                
                if j ==2:
                    # check condition 2 or 3
                    if dist_prev1_next >= A or diff_k_prev1_next >= B:
                        cond = True
                else:
                    # j >=3, need to check prev2 as well
                    # prev2_idx must be valid ( <n )
                    prev2 = prev2_idx
                    dist_prev2_next = abs(X[prev2] - X[next_ball]) + abs(Y[prev2] - Y[next_ball])
                    sum_dist = dist_prev2_next + dist_prev1_next
                    if (dist_prev1_next >= A) or (diff_k_prev1_next >= B) or (sum_dist >= A):
                        cond = True
                
                if cond:
                    new_prev1 = next_ball
                    new_prev2_idx = prev1  # because the new previous is the current prev1
                    if dp[new_mask][new_prev1][new_prev2_idx] < current_len +1:
                        dp[new_mask][new_prev1][new_prev2_idx] = current_len +1
                        if current_len +1 > max_len:
                            max_len = current_len +1
                        queue.append( (new_mask, new_prev1, new_prev2_idx) )
    
    print(max_len)

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