結果

問題 No.704 ゴミ拾い Medium
ユーザー lam6er
提出日時 2025-03-31 17:40:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,943 bytes
コンパイル時間 301 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 240,492 KB
最終ジャッジ日時 2025-03-31 17:42:38
合計ジャッジ時間 15,812 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

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_val = self.tree[(pos << 1) + 1]
            self.tree[pos] = min(left, right_val)
    
    def query_min(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():
    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

    cum_min_A = [0] * n
    DP = [0] * n
    st = SegmentTree(n)
    for i in range(n):
        prev = DP[i-1] if i > 0 else 0
        A_i = prev - x[i] + y[i]
        if i == 0:
            cum_min_A[i] = A_i
        else:
            cum_min_A[i] = min(cum_min_A[i-1], A_i)
        B_i = prev + x[i] + y[i]
        st.update(i, B_i)
        a_i = a[i]
        m_i = bisect.bisect_right(x, a_i) - 1
        candidate_A = cum_min_A[m_i] + a_i if m_i >= 0 else float('inf')
        left = m_i + 1
        right = i
        if left > right:
            candidate_B = float('inf')
        else:
            min_b = st.query_min(left, right)
            candidate_B = min_b - a_i
        DP_i = min(candidate_A, candidate_B)
        DP[i] = DP_i
    print(DP[-1])

if __name__ == '__main__':
    main()
0