結果

問題 No.1117 数列分割
ユーザー lam6er
提出日時 2025-04-15 23:06:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,173 ms / 3,000 ms
コード長 2,220 bytes
コンパイル時間 304 ms
コンパイル使用メモリ 81,908 KB
実行使用メモリ 94,076 KB
最終ジャッジ日時 2025-04-15 23:08:33
合計ジャッジ時間 25,538 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

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

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

    # Initialize DP with two arrays for space optimization
    prev_dp = [-float('inf')] * (N + 1)
    prev_dp[0] = 0  # base case: 0 elements, 0 segments

    for k in range(1, K+1):
        curr_dp = [-float('inf')] * (N + 1)
        que1 = deque()  # for max (dp[j] - S[j])
        que2 = deque()  # for max (dp[j] + S[j])

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

            # Remove outdated elements from the front of the queues
            while que1 and que1[0] < left:
                que1.popleft()
            while que2 and que2[0] < left:
                que2.popleft()

            # Add j = i-1 to the queues if valid
            j = i - 1
            if j >= 0 and prev_dp[j] != -float('inf'):
                val1 = prev_dp[j] - S[j]
                # Maintain que1 in decreasing order of val1
                while que1 and (prev_dp[que1[-1]] - S[que1[-1]] <= val1):
                    que1.pop()
                que1.append(j)
                val2 = prev_dp[j] + S[j]
                # Maintain que2 in decreasing order of val2
                while que2 and (prev_dp[que2[-1]] + S[que2[-1]] <= val2):
                    que2.pop()
                que2.append(j)

            # Calculate the maximum possible value for current i and k
            max_val = -float('inf')
            if que1:
                current_val = (prev_dp[que1[0]] - S[que1[0]]) + S[i]
                if current_val > max_val:
                    max_val = current_val
            if que2:
                current_val = (prev_dp[que2[0]] + S[que2[0]]) - S[i]
                if current_val > max_val:
                    max_val = current_val

            if max_val != -float('inf'):
                curr_dp[i] = max_val

        prev_dp = curr_dp

    print(prev_dp[N])

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