結果

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

ソースコード

diff # 

def main():
    import sys
    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()))
    
    max_color = 51
    possible = [[] for _ in range(max_color)]
    for c in range(max_color):
        for d in range(max_color):
            if abs(c - d) <= K:
                possible[c].append(d)
    
    max_total = 0
    for start in range(n):
        stones = []
        for i in range(n):
            stones.append(A[(i + start) % n])
        colors = []
        for i in range(n):
            colors.append(C[(i + start) % n])
        
        dp = [[[0] * (max_color) for _ in range(n)] for __ in range(n)]
        for i in range(n):
            c = colors[i]
            dp[i][i][c] = stones[i]
        
        for l in range(2, n+1):
            for i in range(n - l + 1):
                j = i + l - 1
                for k in range(i, j):
                    for c1 in range(max_color):
                        if dp[i][k][c1] == 0:
                            continue
                        for c2 in possible[c1]:
                            if c2 >= max_color:
                                continue
                            if dp[k+1][j][c2] == 0:
                                continue
                            total = dp[i][k][c1] + dp[k+1][j][c2]
                            for new_c in [c1, c2]:
                                if new_c >= max_color:
                                    continue
                                if dp[i][j][new_c] < total:
                                    dp[i][j][new_c] = total
        for i in range(n):
            for j in range(i, n):
                for c in range(max_color):
                    if dp[i][j][c] > max_total:
                        max_total = dp[i][j][c]
    print(max_total)

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