結果

問題 No.1117 数列分割
コンテスト
ユーザー LyricalMaestro
提出日時 2025-01-22 01:45:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,424 ms / 3,000 ms
コード長 1,837 bytes
コンパイル時間 377 ms
コンパイル使用メモリ 82,648 KB
実行使用メモリ 166,084 KB
最終ジャッジ日時 2025-01-22 01:46:05
合計ジャッジ時間 16,605 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1117

MIN_VALUE = -10 ** 18

from collections import deque

def main():
    N, K, M = map(int, input().split())
    A = list(map(int, input().split()))

    # Bの累積和計算
    cum_b_list = [0] * (N + 1)
    b = 0
    for i in range(N):
        b += A[i]
        cum_b_list[i + 1] = b

    # スライド最小か
    minus_seg_trees = [deque() for _ in range(K)]
    plus_seg_trees = [ deque() for _ in range(K)]

    dp = [[MIN_VALUE] * (K + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    minus_seg_trees[0].append((0, 0))
    plus_seg_trees[0].append((0, 0))

    for i in range(1, N + 1):
        # 削除フェーズ
        for k in range(K):
            while len(minus_seg_trees[k]) > 0 and minus_seg_trees[k][0][0] < i - M:
                minus_seg_trees[k].popleft()
            while len(plus_seg_trees[k]) > 0 and plus_seg_trees[k][0][0] < i - M:
                plus_seg_trees[k].popleft()

        # 評価フェーズ
        for k in range(1, K + 1):
            if len(minus_seg_trees[k - 1]) > 0 and len(plus_seg_trees[k - 1]) > 0:
                dp[i][k] = max(minus_seg_trees[k - 1][0][1] + cum_b_list[i], plus_seg_trees[k - 1][0][1] - cum_b_list[i])
            
        # 追加フェーズ
        for k in range(K):
            if dp[i][k] > MIN_VALUE:
                x = dp[i][k] - cum_b_list[i]
                while len(minus_seg_trees[k]) > 0 and minus_seg_trees[k][-1][1] < x:
                    minus_seg_trees[k].pop()
                minus_seg_trees[k].append((i, x))

                x = dp[i][k] + cum_b_list[i]
                while len(plus_seg_trees[k]) > 0 and plus_seg_trees[k][-1][1] < x:
                    plus_seg_trees[k].pop()
                plus_seg_trees[k].append((i, x))

    print(dp[-1][K])
    





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