#1036679 (PyPy3) No.1117 数列分割

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
## 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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX