結果

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

ソースコード

diff # 

import sys
import copy

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()))
    
    # 转换为0-based索引
    A = [a for a in A]
    C = [c-1 for c in C]  # 颜色转换为0-based
    
    # 由于是环形，我们将数组复制一倍，处理长度为N的情况
    A_doubled = A + A
    C_doubled = C + C
    
    max_color = 50  # 原题中颜色范围为1-50，转换为0-49
    
    dp = [[[0 for _ in range(max_color)] for __ in range(2*N)] for ___ in range(2*N)]
    
    for i in range(2*N):
        for c in range(max_color):
            dp[i][i][c] = 0
        dp[i][i][C_doubled[i]] = A_doubled[i]
    
    for length in range(2, 2*N+1):
        for l in range(2*N):
            r = l + length - 1
            if r >= 2*N:
                break
            for k in range(l, r):
                for c1 in range(max_color):
                    if dp[l][k][c1] == 0:
                        continue
                    for c2 in range(max_color):
                        if dp[k+1][r][c2] == 0:
                            continue
                        if abs(c1 - c2) > K:
                            continue
                        total = dp[l][k][c1] + dp[k+1][r][c2]
                        if total > dp[l][r][c1]:
                            dp[l][r][c1] = total
                        if total > dp[l][r][c2]:
                            dp[l][r][c2] = total
    
    max_total = 0
    for l in range(N):
        for r in range(l, l + N):
            if r >= 2*N:
                r = r % (2*N)
            for c in range(max_color):
                if dp[l][r][c] > max_total:
                    max_total = dp[l][r][c]
    
    print(max_total)

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