結果

問題 No.1117 数列分割
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-10 20:45:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,087 ms / 3,000 ms
コード長 2,587 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 81,584 KB
実行使用メモリ 129,460 KB
最終ジャッジ日時 2023-10-18 06:49:03
合計ジャッジ時間 26,551 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 64 ms
68,128 KB
testcase_01 AC 64 ms
68,128 KB
testcase_02 AC 63 ms
68,128 KB
testcase_03 AC 687 ms
85,044 KB
testcase_04 AC 270 ms
79,516 KB
testcase_05 AC 63 ms
68,136 KB
testcase_06 AC 145 ms
78,344 KB
testcase_07 AC 149 ms
78,608 KB
testcase_08 AC 397 ms
81,852 KB
testcase_09 AC 352 ms
80,744 KB
testcase_10 AC 421 ms
82,804 KB
testcase_11 AC 767 ms
90,680 KB
testcase_12 AC 1,067 ms
88,476 KB
testcase_13 AC 878 ms
92,408 KB
testcase_14 AC 996 ms
96,336 KB
testcase_15 AC 1,342 ms
89,552 KB
testcase_16 AC 1,443 ms
96,228 KB
testcase_17 AC 407 ms
84,232 KB
testcase_18 AC 1,998 ms
93,504 KB
testcase_19 AC 2,087 ms
91,552 KB
testcase_20 AC 1,071 ms
96,784 KB
testcase_21 AC 1,197 ms
103,452 KB
testcase_22 AC 1,782 ms
129,460 KB
testcase_23 AC 1,799 ms
129,184 KB
testcase_24 AC 1,843 ms
129,244 KB
testcase_25 AC 1,843 ms
128,212 KB
testcase_26 AC 65 ms
68,136 KB
testcase_27 AC 649 ms
86,280 KB
testcase_28 AC 633 ms
85,296 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import accumulate
from typing import Callable, Generic, List, TypeVar


E = TypeVar("E")


class SlidingWindowAggregation(Generic[E]):
    """SlidingWindowAggregation

    Api:
    1. append value to tail,O(1).
    2. pop value from head,O(1).
    3. query aggregated value in window,O(1).
    """

    __slots__ = ["_stack0", "_stack1", "_stack2", "_stack3", "_e0", "_e1", "_size", "_op", "_e"]

    def __init__(self, e: Callable[[], E], op: Callable[[E, E], E]):
        """
        Args:
            e: unit element
            op: merge function
        """
        self._stack0 = []
        self._stack1 = []
        self._stack2 = []
        self._stack3 = []
        self._e = e
        self._e0 = e()
        self._e1 = e()
        self._size = 0
        self._op = op

    def append(self, value: E) -> None:
        if not self._stack0:
            self._push0(value)
            self._transfer()
        else:
            self._push1(value)
        self._size += 1

    def popleft(self) -> None:
        if not self._size:
            return
        if not self._stack0:
            self._transfer()
        self._stack0.pop()
        self._stack2.pop()
        self._e0 = self._stack2[-1] if self._stack2 else self._e()
        self._size -= 1

    def query(self) -> E:
        return self._op(self._e0, self._e1)

    def _push0(self, value):
        self._stack0.append(value)
        self._e0 = self._op(value, self._e0)
        self._stack2.append(self._e0)

    def _push1(self, value):
        self._stack1.append(value)
        self._e1 = self._op(self._e1, value)
        self._stack3.append(self._e1)

    def _transfer(self):
        while self._stack1:
            self._push0(self._stack1.pop())
        while self._stack3:
            self._stack3.pop()
        self._e1 = self._e()

    def __len__(self):
        return self._size


INF = int(1e18)


n, k, m = map(int, input().split())
nums = list(map(int, input().split()))


def max(x, y):
    if x > y:
        return x
    return y


preSum = [0] + list(accumulate(nums))
dp = [-INF] * (n + 1)
dp[0] = 0
for _ in range(k):
    ndp = [-INF] * (n + 1)
    s1 = SlidingWindowAggregation(lambda: -INF, max)
    s2 = SlidingWindowAggregation(lambda: -INF, max)
    for i in range(n + 1):
        ndp[i] = max(ndp[i], s1.query() - preSum[i])
        ndp[i] = max(ndp[i], s2.query() + preSum[i])
        s1.append(dp[i] + preSum[i])
        s2.append(dp[i] - preSum[i])
        if len(s1) > m:
            s1.popleft()
        if len(s2) > m:
            s2.popleft()
    dp = ndp
print(dp[n])
0