結果

問題 No.1117 数列分割
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:03:10
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,544 bytes
コンパイル時間 408 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 265,684 KB
最終ジャッジ日時 2025-04-16 16:10:00
合計ジャッジ時間 23,125 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

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(1, n + 1):
        s[i] = s[i-1] + A[i-1]
    
    INF = float('-inf')
    dp = [[INF] * (K + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    
    for j in range(1, K + 1):
        q1 = deque()  # Maintains max of dp[k][j-1] - s[k]
        q2 = deque()  # Maintains max of dp[k][j-1] + s[k]
        max_i = min(j * M, n)
        for i in range(j, max_i + 1):
            L = max(j-1, i - M)
            k = i - 1
            if dp[k][j-1] != INF:
                val1 = dp[k][j-1] - s[k]
                while q1 and q1[-1][1] <= val1:
                    q1.pop()
                q1.append((k, val1))
                val2 = dp[k][j-1] + s[k]
                while q2 and q2[-1][1] <= val2:
                    q2.pop()
                q2.append((k, val2))
            
            # Remove elements out of the left boundary
            while q1 and q1[0][0] < L:
                q1.popleft()
            while q2 and q2[0][0] < L:
                q2.popleft()
            
            current_max = INF
            if q1:
                current_max = q1[0][1] + s[i]
            if q2:
                current_val = q2[0][1] - s[i]
                current_max = max(current_max, current_val)
            
            if current_max != INF:
                dp[i][j] = current_max
    
    print(dp[n][K])

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