結果
問題 |
No.1117 数列分割
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:17:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,517 ms / 3,000 ms |
コード長 | 1,525 bytes |
コンパイル時間 | 1,537 ms |
コンパイル使用メモリ | 81,396 KB |
実行使用メモリ | 92,552 KB |
最終ジャッジ日時 | 2025-04-15 23:19:02 |
合計ジャッジ時間 | 20,464 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
import sys from collections import deque def main(): n, K, M = map(int, sys.stdin.readline().split()) A = list(map(int, sys.stdin.readline().split())) s = [0] * (n + 1) for i in range(1, n + 1): s[i] = s[i-1] + A[i-1] prev = [-float('inf')] * (n + 1) prev[0] = 0 for k in range(1, K + 1): current = [-float('inf')] * (n + 1) q1 = deque() # Maintains max(prev[j] - s[j]) q2 = deque() # Maintains max(prev[j] + s[j]) max_i = min(k * M, n) for i in range(k, max_i + 1): j = i - 1 if prev[j] != -float('inf'): val1 = prev[j] - s[j] while q1 and (prev[q1[-1]] - s[q1[-1]] <= val1): q1.pop() q1.append(j) val2 = prev[j] + s[j] while q2 and (prev[q2[-1]] + s[q2[-1]] <= val2): q2.pop() q2.append(j) L = max(k-1, i - M) while q1 and q1[0] < L: q1.popleft() while q2 and q2[0] < L: q2.popleft() current_val = -float('inf') if q1: current_val = max(current_val, (prev[q1[0]] - s[q1[0]]) + s[i]) if q2: current_val = max(current_val, (prev[q2[0]] + s[q2[0]]) - s[i]) if current_val != -float('inf'): current[i] = current_val prev = current print(prev[n]) if __name__ == "__main__": main()