結果

問題 No.2423 Merge Stones
ユーザー lam6er
提出日時 2025-04-09 20:56:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,166 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 63,792 KB
最終ジャッジ日時 2025-04-09 20:56:53
合計ジャッジ時間 7,232 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    
    # Extend arrays to handle circular arrangement
    A_ext = A + A
    C_ext = C + C
    n = len(A_ext)
    
    # Precompute prefix sums
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + A_ext[i]
    
    max_sum = max(A)  # At least the maximum single stone
    
    # Initialize possible: possible[i][j] is a set of possible colors
    possible = [[set() for _ in range(n)] for __ in range(n)]
    for i in range(n):
        possible[i][i].add(C_ext[i])
    
    # Precompute allowed colors for each color
    allowed = {}
    max_color = 50
    for c in range(1, max_color + 1):
        low = max(1, c - K)
        high = min(max_color, c + K)
        allowed[c] = set(range(low, high + 1))
    
    # Process intervals in increasing order of length
    for length in range(2, N + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            current = possible[i][j]
            for k in range(i, j):
                left = possible[i][k]
                if not left:
                    continue
                right = possible[k + 1][j]
                if not right:
                    continue
                # Find all valid c1 in left and c2 in right such that |c1 - c2| <= K
                added = set()
                for c1 in left:
                    for c2 in right:
                        if c2 in allowed[c1]:
                            added.add(c1)
                            added.add(c2)
                if added:
                    current.update(added)
            # Check if current interval is valid and update max_sum
            if possible[i][j]:
                current_sum = prefix[j + 1] - prefix[i]
                if current_sum > max_sum:
                    max_sum = current_sum
    # Also check intervals in the original array's length
    print(max_sum)

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