結果

問題 No.2423 Merge Stones
ユーザー gew1fw
提出日時 2025-06-12 14:53:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,656 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 129,336 KB
最終ジャッジ日時 2025-06-12 14:56:17
合計ジャッジ時間 6,844 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

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()))
    N = len(A)

    # 复制数组处理环
    A = A * 2
    C = C * 2

    max_len = N
    dp = [[defaultdict(int) for _ in range(2*N)] for _ in range(2*N)]

    # 初始化
    for i in range(2*N):
        dp[i][i][C[i]] = A[i]

    for length in range(2, max_len + 1):
        for l in range(2*N - length + 1):
            r = l + length - 1
            if r >= 2*N:
                break
            # 尝试拆分成两部分
            for mid in range(l, r):
                # 左边[l, mid]，右边[mid+1, r]
                # 检查是否有颜色对满足条件
                for c1 in dp[l][mid]:
                    for c2 in dp[mid+1][r]:
                        if abs(c1 - c2) <= K:
                            sum_val = dp[l][mid][c1] + dp[mid+1][r][c2]
                            # 可以选择任意颜色
                            for new_c in [c1, c2]:
                                if sum_val > dp[l][r][new_c]:
                                    dp[l][r][new_c] = sum_val

    # 处理环的情况，寻找最大值
    max_sum = 0
    for l in range(N):
        for r in range(l, l + N):
            if r >= 2*N:
                break
            current = dp[l][r]
            if current:
                for c in current:
                    if current[c] > max_sum:
                        max_sum = current[c]
    print(max_sum)

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