結果
問題 |
No.1117 数列分割
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:14:22 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,451 bytes |
コンパイル時間 | 350 ms |
コンパイル使用メモリ | 81,620 KB |
実行使用メモリ | 82,924 KB |
最終ジャッジ日時 | 2025-04-15 23:17:06 |
合計ジャッジ時間 | 6,198 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 WA * 5 |
ソースコード
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_dp = [-float('inf')] * (N + 1) prev_dp[0] = 0 # Base case: 0 elements split into 0 subarrays for j in range(1, K + 1): current_dp = [-float('inf')] * (N + 1) remaining_subseq = K - j min_remaining = remaining_subseq * 1 max_remaining = remaining_subseq * M i_min = max(j, N - max_remaining) i_max = min(N - min_remaining, j * M) if i_min > i_max: prev_dp = current_dp continue max_queue1 = deque() # Stores (k, prev_dp[k] - S[k]) max_queue2 = deque() # Stores (k, prev_dp[k] + S[k]) for i in range(i_min, i_max + 1): k_start = i - M # Add k = i-1 to the queues if valid k = i - 1 if k >= 0 and prev_dp[k] != -float('inf'): val1 = prev_dp[k] - S[k] # Maintain max_queue1 in decreasing order while max_queue1 and max_queue1[-1][1] <= val1: max_queue1.pop() max_queue1.append((k, val1)) val2 = prev_dp[k] + S[k] # Maintain max_queue2 in decreasing order while max_queue2 and max_queue2[-1][1] <= val2: max_queue2.pop() max_queue2.append((k, val2)) # Remove elements out of the current window [k_start, i-1] while max_queue1 and max_queue1[0][0] < k_start: max_queue1.popleft() while max_queue2 and max_queue2[0][0] < k_start: max_queue2.popleft() max_val = -float('inf') if max_queue1: current_val1 = max_queue1[0][1] + S[i] max_val = current_val1 if max_queue2: current_val2 = max_queue2[0][1] - S[i] if current_val2 > max_val: max_val = current_val2 if max_val != -float('inf'): current_dp[i] = max_val prev_dp = current_dp result = prev_dp[N] if prev_dp[N] != -float('inf') else 0 print(result) if __name__ == '__main__': main()