結果

問題 No.2423 Merge Stones
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:49:22
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,660 bytes
コンパイル時間 290 ms
コンパイル使用メモリ 82,260 KB
実行使用メモリ 259,392 KB
最終ジャッジ日時 2025-06-12 14:52:58
合計ジャッジ時間 6,694 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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()))
    
    INF = -10**18
    MAX_COLOR = 50
    
    # 处理环状结构，复制数组
    A = A * 2
    C = C * 2
    max_length = N
    
    # 初始化dp
    dp = [[[INF for _ in range(MAX_COLOR+1)] for __ in range(2*N)] for ___ in range(2*N)]
    
    for i in range(2*N):
        c = C[i]
        dp[i][i][c] = A[i]
    
    for length in range(2, max_length + 1):
        for i in range(2*N):
            j = i + length - 1
            if j >= 2*N:
                break
            for k in range(i, j):
                for c1 in range(1, MAX_COLOR + 1):
                    if dp[i][k][c1] == INF:
                        continue
                    for c2 in range(1, MAX_COLOR + 1):
                        if dp[k+1][j][c2] == INF:
                            continue
                        if abs(c1 - c2) <= K:
                            new_sum = dp[i][k][c1] + dp[k+1][j][c2]
                            if new_sum > dp[i][j][c1]:
                                dp[i][j][c1] = new_sum
                            if new_sum > dp[i][j][c2]:
                                dp[i][j][c2] = new_sum
    
    max_result = 0
    for i in range(N):
        for j in range(i, 2*N):
            if j - i + 1 > N:
                continue
            for c in range(1, MAX_COLOR + 1):
                if dp[i][j][c] > max_result:
                    max_result = dp[i][j][c]
    print(max_result)

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