結果

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

ソースコード

diff # 

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