結果

問題 No.2423 Merge Stones
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:58:39
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,686 bytes
コンパイル時間 217 ms
コンパイル使用メモリ 82,224 KB
実行使用メモリ 115,400 KB
最終ジャッジ日時 2025-06-12 21:02:12
合計ジャッジ時間 6,774 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    sys.setrecursionlimit(1 << 25)
    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 + A
    C = C + C
    n = len(A)  # Now n is 2*N
    
    # Initialize DP
    dp = [[dict() for _ in range(n)] for __ in range(n)]
    max_sum = 0
    
    for i in range(n):
        c = C[i]
        val = A[i]
        dp[i][i][c] = val
        if val > max_sum:
            max_sum = val
    
    # Process intervals of length L from 2 to N
    for L in range(2, N+1):
        for i in range(n - L + 1):
            j = i + L - 1
            current_dp = {}
            # Split into two parts: i..k and k+1..j
            for k in range(i, j):
                left_dp = dp[i][k]
                right_dp = dp[k+1][j]
                for c1 in left_dp:
                    for c2 in right_dp:
                        if abs(c1 - c2) <= K:
                            total = left_dp[c1] + right_dp[c2]
                            for new_c in [c1, c2]:
                                if new_c in current_dp:
                                    if total > current_dp[new_c]:
                                        current_dp[new_c] = total
                                else:
                                    current_dp[new_c] = total
            if current_dp:
                dp[i][j] = current_dp
                current_max = max(current_dp.values())
                if current_max > max_sum:
                    max_sum = current_max
    
    print(max_sum)

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