結果
問題 |
No.1117 数列分割
|
ユーザー |
|
提出日時 | 2023-03-10 20:45:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,839 ms / 3,000 ms |
コード長 | 2,587 bytes |
コンパイル時間 | 261 ms |
コンパイル使用メモリ | 82,124 KB |
実行使用メモリ | 129,796 KB |
最終ジャッジ日時 | 2024-09-18 03:23:20 |
合計ジャッジ時間 | 21,870 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
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])