結果

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

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx +=1
    K = int(input[idx])
    idx +=1
    A = list(map(int, input[idx:idx+N]))
    idx +=N
    C = list(map(int, input[idx:idx+N]))
    idx +=N
    
    max_color = 50
    size = 2 * N
    dp = [ [ [0]*(max_color +1) for _ in range(size +1)] for __ in range(size +1)]
    
    A_extended = A + A
    C_extended = C + C
    
    for i in range(1, size +1):
        c = C_extended[i-1]
        a = A_extended[i-1]
        dp[i][i][c] = a
    
    for l in range(2, N+1):
        for i in range(1, size +1 - l +1):
            j = i + l -1
            if j > size:
                continue
            for k in range(i, j):
                for c_prev in range(1, max_color +1):
                    if dp[i][k][c_prev] ==0:
                        continue
                    min_c = max(1, c_prev - K)
                    max_c = min(max_color, c_prev + K)
                    for c_next in range(min_c, max_c +1):
                        if dp[k+1][j][c_next] ==0:
                            continue
                        sum_m = dp[i][k][c_prev] + dp[k+1][j][c_next]
                        if sum_m > dp[i][j][c_prev]:
                            dp[i][j][c_prev] = sum_m
                        if sum_m > dp[i][j][c_next]:
                            dp[i][j][c_next] = sum_m
    
    max_val = 0
    for i in range(1, N+1):
        for j in range(i, i + N):
            j_mod = j % size
            if j_mod ==0:
                j_mod = size
            if j_mod < i:
                continue
            for c in range(1, max_color +1):
                if dp[i][j][c] > max_val:
                    max_val = dp[i][j][c]
    print(max_val)

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