結果

問題 No.704 ゴミ拾い Medium
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0