結果

問題 No.2423 Merge Stones
ユーザー qwewe
提出日時 2025-04-24 12:22:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,431 bytes
コンパイル時間 318 ms
コンパイル使用メモリ 82,708 KB
実行使用メモリ 90,024 KB
最終ジャッジ日時 2025-04-24 12:24:24
合計ジャッジ時間 6,460 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    C = list(map(int, sys.stdin.readline().split()))
    
    # Duplicate the arrays to handle circularity
    A = A * 2
    C = C * 2
    
    # Precompute sum[i][j] for all i <= j < 2N
    sum_ = [[0] * (2 * N) for _ in range(2 * N)]
    for i in range(2 * N):
        current_sum = 0
        for j in range(i, 2 * N):
            current_sum += A[j]
            sum_[i][j] = current_sum
    
    # Precompute allowed masks for each color
    allowed_masks = [0] * 51  # colors are 1..50
    for c1 in range(1, 51):
        mask = 0
        for c2 in range(1, 51):
            if abs(c1 - c2) <= K:
                mask |= 1 << c2
        allowed_masks[c1] = mask
    
    # Initialize DP masks
    mask = [[0] * (2 * N) for _ in range(2 * N)]
    for i in range(2 * N):
        c = C[i]
        mask[i][i] = 1 << c
    
    # Fill DP table
    for length in range(2, N + 1):
        for i in range(2 * N - length + 1):
            j = i + length - 1
            if j - i + 1 > N:
                continue
            current_mask = 0
            for k in range(i, j):
                left_mask = mask[i][k]
                right_mask = mask[k+1][j]
                if left_mask == 0 or right_mask == 0:
                    continue
                # Process all colors in left_mask
                temp_left = left_mask
                while temp_left:
                    # Extract the least significant bit
                    lsb = temp_left & -temp_left
                    c1 = (lsb).bit_length() - 1
                    temp_left ^= lsb
                    # Get allowed colors for c1 and check overlap with right_mask
                    allowed = allowed_masks[c1]
                    overlap = allowed & right_mask
                    if overlap:
                        current_mask |= (1 << c1) | overlap
            mask[i][j] = current_mask
    
    # Find the maximum sum among all valid intervals
    max_sum = max(A[:N])  # Initialize with the maximum single stone
    for i in range(N):
        for j in range(i, i + N):
            if j >= 2 * N:
                break
            if mask[i][j] != 0:
                current_sum = sum_[i][j]
                if current_sum > max_sum:
                    max_sum = current_sum
    print(max_sum)

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