結果

問題 No.1117 数列分割
ユーザー lam6er
提出日時 2025-03-20 18:54:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,121 ms / 3,000 ms
コード長 1,925 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 82,888 KB
実行使用メモリ 94,780 KB
最終ジャッジ日時 2025-03-20 18:56:51
合計ジャッジ時間 24,827 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N, K, M = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    S = [0] * (N + 1)
    for i in range(N):
        S[i + 1] = S[i] + A[i]

    prev_dp = [-float('inf')] * (N + 1)
    prev_dp[0] = 0  # base case: 0 elements, 0 partitions

    for _ in range(K):
        curr_dp = [-float('inf')] * (N + 1)
        max_deque1 = deque()  # for (value, index) in prev_dp[i] - S[i]
        max_deque2 = deque()  # for (value, index) in prev_dp[i] + S[i]

        for j in range(1, N + 1):
            i = j - 1
            L = max(0, j - M)

            # Remove out of window elements from deque
            while max_deque1 and max_deque1[0][1] < L:
                max_deque1.popleft()
            while max_deque2 and max_deque2[0][1] < L:
                max_deque2.popleft()

            # Add current i if valid
            if prev_dp[i] != -float('inf'):
                current_val1 = prev_dp[i] - S[i]
                current_val2 = prev_dp[i] + S[i]

                # Maintain max_deque1 in decreasing order
                while max_deque1 and max_deque1[-1][0] <= current_val1:
                    max_deque1.pop()
                max_deque1.append((current_val1, i))

                # Maintain max_deque2 in decreasing order
                while max_deque2 and max_deque2[-1][0] <= current_val2:
                    max_deque2.pop()
                max_deque2.append((current_val2, i))

            # Calculate the current maximum values
            max1 = max_deque1[0][0] if max_deque1 else -float('inf')
            max2 = max_deque2[0][0] if max_deque2 else -float('inf')
            curr_val = max(max1 + S[j], max2 - S[j])

            if curr_val != -float('inf'):
                curr_dp[j] = max(curr_dp[j], curr_val)

        prev_dp = curr_dp

    print(prev_dp[N])

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