結果
問題 |
No.704 ゴミ拾い Medium
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:48:27 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,087 bytes |
コンパイル時間 | 176 ms |
コンパイル使用メモリ | 82,524 KB |
実行使用メモリ | 227,988 KB |
最終ジャッジ日時 | 2025-03-20 20:48:43 |
合計ジャッジ時間 | 15,039 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 42 WA * 2 |
ソースコード
import bisect import heapq def main(): import sys input = sys.stdin.read().split() ptr = 0 n = int(input[ptr]) ptr +=1 a = list(map(int, input[ptr:ptr+n])) ptr +=n x = list(map(int, input[ptr:ptr+n])) ptr +=n y = list(map(int, input[ptr:ptr+n])) ptr +=n events = [[] for _ in range(n)] dp = [0] * n # Group1: min-heap of cj1 (for j in group1) group1_heap = [] # Group2: min-heap of (cj2, j), and need to check validity group2_heap = [] groups2_valid = [False]*n # True means it's still valid in group2 for k in range(n): j = k xj = x[j] pos = bisect.bisect_left(a, xj) if pos >= n: pos = n - 1 kj = pos if kj <= k: cj1 = (dp[j-1] if j-1 >=0 else 0) - xj + y[j] heapq.heappush(group1_heap, cj1) else: cj2 = (dp[j-1] if j-1 >=0 else 0) + xj + y[j] heapq.heappush(group2_heap, (cj2, j)) groups2_valid[j] = True if kj < n: events[kj].append(j) # Process events for current k for j in events[k]: if groups2_valid[j]: groups2_valid[j] = False cj1 = (dp[j-1] if j-1 >=0 else 0) - x[j] + y[j] heapq.heappush(group1_heap, cj1) # Compute group1_min group1_min = None if group1_heap: group1_min = group1_heap[0] # Compute group2_min group2_min = None while group2_heap: cj2, j = group2_heap[0] if groups2_valid[j]: group2_min = cj2 break else: heapq.heappop(group2_heap) current_min = float('inf') if group1_min is not None: current_min = min(current_min, group1_min + a[k]) if group2_min is not None: current_min = min(current_min, group2_min - a[k]) dp[k] = current_min print(dp[-1]) if __name__ == '__main__': main()