結果

問題 No.1117 数列分割
ユーザー lam6er
提出日時 2025-04-15 23:11:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,482 ms / 3,000 ms
コード長 1,525 bytes
コンパイル時間 436 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 92,544 KB
最終ジャッジ日時 2025-04-15 23:13:55
合計ジャッジ時間 18,152 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(1, n + 1):
        s[i] = s[i-1] + A[i-1]
    
    prev = [-float('inf')] * (n + 1)
    prev[0] = 0
    
    for k in range(1, K + 1):
        current = [-float('inf')] * (n + 1)
        q1 = deque()  # Maintains max(prev[j] - s[j])
        q2 = deque()  # Maintains max(prev[j] + s[j])
        max_i = min(k * M, n)
        for i in range(k, max_i + 1):
            j = i - 1
            if prev[j] != -float('inf'):
                val1 = prev[j] - s[j]
                while q1 and (prev[q1[-1]] - s[q1[-1]] <= val1):
                    q1.pop()
                q1.append(j)
                val2 = prev[j] + s[j]
                while q2 and (prev[q2[-1]] + s[q2[-1]] <= val2):
                    q2.pop()
                q2.append(j)
            L = max(k-1, i - M)
            while q1 and q1[0] < L:
                q1.popleft()
            while q2 and q2[0] < L:
                q2.popleft()
            
            current_val = -float('inf')
            if q1:
                current_val = max(current_val, (prev[q1[0]] - s[q1[0]]) + s[i])
            if q2:
                current_val = max(current_val, (prev[q2[0]] + s[q2[0]]) - s[i])
            if current_val != -float('inf'):
                current[i] = current_val
        prev = current
    
    print(prev[n])

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