結果
問題 | No.704 ゴミ拾い Medium |
ユーザー |
![]() |
提出日時 | 2025-03-20 20:44:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 505 ms / 1,500 ms |
コード長 | 3,349 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 82,636 KB |
実行使用メモリ | 221,920 KB |
最終ジャッジ日時 | 2025-03-20 20:44:46 |
合計ジャッジ時間 | 10,703 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 44 |
ソースコード
import bisect def main(): import sys input = sys.stdin.read().split() idx = 0 n = int(input[idx]) idx += 1 a = list(map(int, input[idx:idx+n])) idx +=n x = list(map(int, input[idx:idx+n])) idx +=n y = list(map(int, input[idx:idx+n])) idx +=n dp = [0] * n min_left = float('inf') last_left_j = -1 from collections import deque dq = deque() for i in range(n): ai = a[i] if i == 0: # Handle i=0 separately j_prime = bisect.bisect_right(x, ai, 0, 1) - 1 # Case 2: j in 0..j_prime current_min_left = float('inf') for j in range(j_prime +1): val = (0 if j == 0 else dp[j-1]) - x[j] + y[j] if val < current_min_left: current_min_left = val case2 = current_min_left + ai if j_prime >=0 else float('inf') # Case 1: j'_{i}+1 ... i left_bound = j_prime +1 case1 = float('inf') if left_bound <=i: val = (0 if i ==0 else dp[i-1]) + x[i] + y[i] while dq and dq[-1][1] >= val: dq.pop() dq.append( (i, val) ) # pop from front where j < left_bound while dq and dq[0][0] < left_bound: dq.popleft() if dq: case1 = dq[0][1] - ai dp[i] = min(case2, case1) # update min_left for i=0, which may not be needed since for i=0, we computed current_min_left directly # but for the structure, here min_left starts current_val = (0 -x[0] + y[0]) if 0 <=j_prime else float('inf') min_left = current_val last_left_j = j_prime else: # binary search j'_i in x[0..i] j_prime = bisect.bisect_right(x, ai, 0, i+1) -1 # Update min_left by processing j from last_left_j +1 to j_prime if last_left_j < j_prime: start = last_left_j +1 end = j_prime for j in range(start, end+1): prev_dp = dp[j-1] if j >=1 else 0 val = prev_dp - x[j] + y[j] if val < min_left: min_left = val last_left_j = j_prime # Compute case2_candidate if j_prime >=0: case2_candidate = min_left + ai else: case2_candidate = float('inf') # Handle case1: j >= j_prime +1, up to i left_bound = j_prime +1 # add j=i to deque if applicable if left_bound <= i: prev_dp_i = dp[i-1] if i-1 >=0 else 0 val = prev_dp_i + x[i] + y[i] # add to deque while dq and dq[-1][1] >= val: dq.pop() dq.append( (i, val) ) # now, remove elements from deque with j < left_bound while dq and dq[0][0] < left_bound: dq.popleft() # compute case1_candidate if dq: case1_candidate = dq[0][1] - ai else: case1_candidate = float('inf') dp[i] = min(case2_candidate, case1_candidate) print(dp[-1]) if __name__ == '__main__': main()