結果

問題 No.1117 数列分割
ユーザー lam6er
提出日時 2025-03-31 17:30:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,468 bytes
コンパイル時間 132 ms
コンパイル使用メモリ 82,472 KB
実行使用メモリ 101,568 KB
最終ジャッジ日時 2025-03-31 17:31:21
合計ジャッジ時間 22,638 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr]); ptr += 1
    K = int(input[ptr]); ptr += 1
    M = int(input[ptr]); ptr += 1
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N

    # Prefix sum array
    s = [0] * (N + 1)
    for i in range(1, N+1):
        s[i] = s[i-1] + A[i-1]

    # DP with two rolling arrays
    prev = [-float('inf')] * (N + 1)
    prev[0] = 0  # base case: 0 elements divided into 0 groups gives sum 0

    for j in range(1, K + 1):
        curr = [-float('inf')] * (N + 1)
        a_queue = deque()  # to track max( dp_prev[k] + s[k] )
        b_queue = deque()  # to track max( dp_prev[k] - s[k] )

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

            # Remove out-of-window elements from queues
            while a_queue and a_queue[0] < left:
                a_queue.popleft()
            while b_queue and b_queue[0] < left:
                b_queue.popleft()

            # Add new candidate k = i-1 to the queues if possible
            k = i - 1
            if prev[k] != -float('inf'):
                a_val = prev[k] + s[k]
                b_val = prev[k] - s[k]

                # Maintain a_queue in decreasing order
                while a_queue and a_val >= (prev[a_queue[-1]] + s[a_queue[-1]]):
                    a_queue.pop()
                a_queue.append(k)

                # Maintain b_queue in decreasing order
                while b_queue and b_val >= (prev[b_queue[-1]] - s[b_queue[-1]]):
                    b_queue.pop()
                b_queue.append(k)

            # Calculate current maximum
            max_a = -float('inf')
            if a_queue:
                max_a = prev[a_queue[0]] + s[a_queue[0]]
            max_b = -float('inf')
            if b_queue:
                max_b = prev[b_queue[0]] - s[b_queue[0]]

            current_max = -float('inf')
            if max_a != -float('inf') or max_b != -float('inf'):
                if max_a != -float('inf') and max_b != -float('inf'):
                    current_max = max(max_a - s[i], max_b + s[i])
                elif max_a != -float('inf'):
                    current_max = max_a - s[i]
                else:
                    current_max = max_b + s[i]
            if current_max != -float('inf'):
                curr[i] = current_max

        prev = curr

    print(prev[N])

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