結果

問題 No.1117 数列分割
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:59:40
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,611 bytes
コンパイル時間 603 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 264,808 KB
最終ジャッジ日時 2025-04-16 16:03:00
合計ジャッジ時間 23,181 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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()))
    
    sums = [0] * (N + 1)
    for i in range(1, N + 1):
        sums[i] = sums[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):
        max1_q = deque()  # (k, dp[k][j-1] - sums[k])
        max2_q = deque()  # (k, dp[k][j-1] + sums[k])
        max_i = min(j * M, N)
        for i in range(j, max_i + 1):
            k = i - 1
            if k >= 0 and dp[k][j-1] != INF:
                val1 = dp[k][j-1] - sums[k]
                while max1_q and max1_q[-1][1] <= val1:
                    max1_q.pop()
                max1_q.append((k, val1))
                
                val2 = dp[k][j-1] + sums[k]
                while max2_q and max2_q[-1][1] <= val2:
                    max2_q.pop()
                max2_q.append((k, val2))
            
            lower_bound = max(j-1, i - M)
            while max1_q and max1_q[0][0] < lower_bound:
                max1_q.popleft()
            while max2_q and max2_q[0][0] < lower_bound:
                max2_q.popleft()
            
            current_max = INF
            if max1_q:
                current_max = max(current_max, max1_q[0][1] + sums[i])
            if max2_q:
                current_max = max(current_max, max2_q[0][1] - sums[i])
            
            if current_max != INF:
                dp[i][j] = current_max
    
    print(dp[N][K])

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