結果
問題 |
No.2139 K Consecutive Sushi
|
ユーザー |
|
提出日時 | 2025-07-12 01:27:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 315 ms / 2,000 ms |
コード長 | 2,146 bytes |
コンパイル時間 | 393 ms |
コンパイル使用メモリ | 82,232 KB |
実行使用メモリ | 117,028 KB |
最終ジャッジ日時 | 2025-07-12 01:27:41 |
合計ジャッジ時間 | 8,565 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
## https://yukicoder.me/problems/no/1645 MIN_VALUE = -10 ** 18 class SegmentTree: """ 非再帰版セグメント木。 更新は「加法」、取得は「最大値」のもの限定。 """ def __init__(self, init_array): n = 1 while n < len(init_array): n *= 2 self.size = n self.array = [MIN_VALUE] * (2 * self.size) for i, a in enumerate(init_array): self.array[self.size + i] = a end_index = self.size start_index = end_index // 2 while start_index >= 1: for i in range(start_index, end_index): self.array[i] = max(self.array[2 * i], self.array[2 * i + 1]) end_index = start_index start_index = end_index // 2 def set(self, x, a): index = self.size + x self.array[index] = a while index > 1: index //= 2 self.array[index] = max(self.array[2 * index], self.array[2 * index + 1]) def get_max(self, l, r): L = self.size + l; R = self.size + r # 2. 区間[l, r)の最大値を求める s = MIN_VALUE while L < R: if R & 1: R -= 1 s = max(s, self.array[R]) if L & 1: s = max(s, self.array[L]) L += 1 L >>= 1; R >>= 1 return s def main(): N, K = map(int, input().split()) A = list(map(int, input().split())) dp = [[MIN_VALUE] * (N + 1) for _ in range(2)] dp[0][0] = 0 cum_a_list = [0] * (N + 1) a = 0 for i in range(N): a += A[i] cum_a_list[i + 1] = a seg_tree = SegmentTree([MIN_VALUE] * (N + 1)) seg_tree.set(0, dp[0][0]) for i in range(N): m = seg_tree.get_max(max(i + 1 - (K - 1), 0), i + 1) x = cum_a_list[i + 1] + m dp[1][i + 1] = max(dp[1][i + 1], x) dp[0][i + 1] = max(dp[0][i + 1], dp[1][i], dp[0][i]) seg_tree.set(i + 1, dp[0][i + 1] - cum_a_list[i + 1]) print(max(dp[0][-1], dp[1][-1])) if __name__ == "__main__": main()