結果
問題 |
No.860 買い物
|
ユーザー |
![]() |
提出日時 | 2025-03-26 15:58:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 448 ms / 1,000 ms |
コード長 | 2,691 bytes |
コンパイル時間 | 300 ms |
コンパイル使用メモリ | 82,316 KB |
実行使用メモリ | 128,164 KB |
最終ジャッジ日時 | 2025-03-26 15:59:36 |
合計ジャッジ時間 | 4,957 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
import sys class SegmentTree: def __init__(self, size): self.n = 1 while self.n < size: self.n <<= 1 self.size = size self.tree = [float('inf')] * (2 * self.n) def update(self, pos, value): pos += self.n self.tree[pos] = value while pos > 1: pos >>= 1 left = self.tree[pos << 1] right = self.tree[(pos << 1) + 1] self.tree[pos] = min(left, right) def query_range(self, l, r): res = float('inf') l += self.n r += self.n while l <= r: if l % 2 == 1: res = min(res, self.tree[l]) l += 1 if r % 2 == 0: res = min(res, self.tree[r]) r -= 1 l >>= 1 r >>= 1 return res def main(): input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx += 1 C = [] D = [] for _ in range(N): c = int(input[idx]) d = int(input[idx+1]) C.append(c) D.append(d) idx += 2 prefix_C = [0] * (N + 1) for i in range(N): prefix_C[i+1] = prefix_C[i] + C[i] prefix_D = [0] * (N + 1) for i in range(N): prefix_D[i+1] = prefix_D[i] + D[i] min_prefix = [0] * N min_prefix[0] = C[0] for i in range(1, N): min_prefix[i] = min(min_prefix[i-1], C[i]) left = [-1] * N stack = [] for i in range(N): while stack and C[stack[-1]] >= C[i]: stack.pop() if stack: left[i] = stack[-1] else: left[i] = -1 stack.append(i) st = SegmentTree(N) dp = [0] * N val = [0] * N A_minus1 = -prefix_D[1] # A[-1] = 0 - 0 - prefix_D[1] = -D[0] for i in range(N): l = left[i] q_l = max(l, 0) q_r = i - 1 if q_l > q_r: group2_min = float('inf') else: group2 = st.query_range(q_l, q_r) group2_min = group2 + C[i] if group2 != float('inf') else float('inf') group1_min = val[l] if l >= 0 else float('inf') current_val = min(group2_min, group1_min) candidate_jm1 = A_minus1 + min_prefix[i] current_total = prefix_C[i+1] + prefix_D[i+1] dp_i = current_total + min(current_val, candidate_jm1) dp[i] = dp_i val[i] = current_val if i + 2 <= N: d_part = prefix_D[i+2] else: d_part = 0 a_i = dp_i - prefix_C[i+1] - d_part st.update(i, a_i) print(dp[-1]) if __name__ == '__main__': main()