結果

問題 No.1117 数列分割
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:12:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,451 bytes
コンパイル時間 378 ms
コンパイル使用メモリ 82,572 KB
実行使用メモリ 82,364 KB
最終ジャッジ日時 2025-04-15 23:14:15
合計ジャッジ時間 6,313 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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_dp = [-float('inf')] * (N + 1)
    prev_dp[0] = 0  # Base case: 0 elements split into 0 subarrays
    
    for j in range(1, K + 1):
        current_dp = [-float('inf')] * (N + 1)
        remaining_subseq = K - j
        min_remaining = remaining_subseq * 1
        max_remaining = remaining_subseq * M
        
        i_min = max(j, N - max_remaining)
        i_max = min(N - min_remaining, j * M)
        
        if i_min > i_max:
            prev_dp = current_dp
            continue
        
        max_queue1 = deque()  # Stores (k, prev_dp[k] - S[k])
        max_queue2 = deque()  # Stores (k, prev_dp[k] + S[k])
        
        for i in range(i_min, i_max + 1):
            k_start = i - M
            # Add k = i-1 to the queues if valid
            k = i - 1
            if k >= 0 and prev_dp[k] != -float('inf'):
                val1 = prev_dp[k] - S[k]
                # Maintain max_queue1 in decreasing order
                while max_queue1 and max_queue1[-1][1] <= val1:
                    max_queue1.pop()
                max_queue1.append((k, val1))
                
                val2 = prev_dp[k] + S[k]
                # Maintain max_queue2 in decreasing order
                while max_queue2 and max_queue2[-1][1] <= val2:
                    max_queue2.pop()
                max_queue2.append((k, val2))
            
            # Remove elements out of the current window [k_start, i-1]
            while max_queue1 and max_queue1[0][0] < k_start:
                max_queue1.popleft()
            while max_queue2 and max_queue2[0][0] < k_start:
                max_queue2.popleft()
            
            max_val = -float('inf')
            if max_queue1:
                current_val1 = max_queue1[0][1] + S[i]
                max_val = current_val1
            if max_queue2:
                current_val2 = max_queue2[0][1] - S[i]
                if current_val2 > max_val:
                    max_val = current_val2
            if max_val != -float('inf'):
                current_dp[i] = max_val
        
        prev_dp = current_dp
    
    result = prev_dp[N] if prev_dp[N] != -float('inf') else 0
    print(result)

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