結果

問題 No.2423 Merge Stones
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:57:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,653 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 113,436 KB
最終ジャッジ日時 2025-06-12 14:58:52
合計ジャッジ時間 6,635 ms
ジャッジサーバーID
（参考情報） 		judge4 / 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 = 51  # since C_i can be up to 50
    allowed = [[False] * (max_color + 1) for _ in range(max_color + 1)]
    for c1 in range(max_color + 1):
        for c2 in range(max_color + 1):
            if abs(c1 - c2) <= K:
                allowed[c1][c2] = True

    # To handle the circular case, we duplicate the arrays
    A_dup = A * 2
    C_dup = C * 2

    # Initialize DP table
    dp = [[{} for _ in range(2 * n)] for __ in range(2 * n)]
    for i in range(2 * n):
        dp[i][i][C_dup[i]] = A_dup[i]

    for l in range(2, n + 1):
        for i in range(2 * n):
            j = i + l - 1
            if j >= 2 * n:
                continue
            for k in range(i, j):
                for c1 in dp[i][k]:
                    for c2 in dp[k+1][j]:
                        if allowed[c1][c2]:
                            new_sum = dp[i][k][c1] + dp[k+1][j][c2]
                            for new_c in [c1, c2]:
                                if new_c in dp[i][j]:
                                    if new_sum > dp[i][j][new_c]:
                                        dp[i][j][new_c] = new_sum
                                else:
                                    dp[i][j][new_c] = new_sum

    max_val = 0
    for i in range(n):
        for j in range(i, i + n):
            for c in dp[i][j]:
                if dp[i][j][c] > max_val:
                    max_val = dp[i][j][c]
    print(max_val)

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