結果

問題 No.2423 Merge Stones
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:55:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,022 bytes
コンパイル時間 1,076 ms
コンパイル使用メモリ 82,392 KB
実行使用メモリ 77,292 KB
最終ジャッジ日時 2025-06-12 19:56:47
合計ジャッジ時間 7,035 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    C = list(map(int, sys.stdin.readline().split()))
    
    max_color = 50
    INF = -float('inf')
    
    # 预处理环的情况，固定一个起点，拆成线性结构
    max_sum = 0
    for start in range(N):
        linear_A = A[start:] + A[:start]
        linear_C = C[start:] + C[:start]
        
        # 初始化动态规划表
        dp = [[[INF] * (max_color + 1) for _ in range(N)] for __ in range(N)]
        
        for i in range(N):
            color = linear_C[i]
            dp[i][i][color] = linear_A[i]
            if linear_A[i] > max_sum:
                max_sum = linear_A[i]
        
        for length in range(2, N+1):
            for l in range(N - length + 1):
                r = l + length - 1
                for m in range(l, r):
                    for c1 in range(len(dp[l][m])):
                        if dp[l][m][c1] == INF:
                            continue
                        for c2 in range(len(dp[m+1][r])):
                            if dp[m+1][r][c2] == INF:
                                continue
                            if abs(c1 - c2) <= K:
                                total = dp[l][m][c1] + dp[m+1][r][c2]
                                if dp[l][r][c1] < total:
                                    dp[l][r][c1] = total
                                if dp[l][r][c2] < total:
                                    dp[l][r][c2] = total
        
        for l in range(N):
            for r in range(l, N):
                for c in range(len(dp[l][r])):
                    if dp[l][r][c] != INF and dp[l][r][c] > max_sum:
                        max_sum = dp[l][r][c]
        
        # 处理环的连接情况，考虑起点和终点是否相邻
        # 此处可以进一步优化，例如将起点和终点视为相邻，判断是否可以合并
        
    print(max_sum)

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