結果

問題 No.860 買い物
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:58:31
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 159 ms / 1,000 ms
コード長 1,324 bytes
コンパイル時間 253 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 86,656 KB
最終ジャッジ日時 2025-03-31 17:59:09
合計ジャッジ時間 3,446 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    C = []
    D = []
    for _ in range(N):
        c, d = map(int, sys.stdin.readline().split())
        C.append(c)
        D.append(d)
    
    sum_c = [0] * (N + 1)
    sum_d = [0] * (N + 1)
    for i in range(N):
        sum_c[i + 1] = sum_c[i] + C[i]
        sum_d[i + 1] = sum_d[i] + D[i]
    
    dp = [0] * (N + 1)
    # The deque stores tuples (current_min_C, current_min_val, start_index)
    q = deque()
    
    for i in range(1, N + 1):
        current_c = C[i - 1]
        current_min_val = dp[i - 1] - sum_c[i - 1] - sum_d[i]
        # Maintain the deque to remove elements with C >= current_c
        while q and q[-1][0] >= current_c:
            current_min_val = min(current_min_val, q[-1][1])
            q.pop()
        q.append((current_c, current_min_val, i - 1))
        
        # Now find the best j
        min_total = float('inf')
        # Check all possible elements in the deque
        for idx in range(len(q)):
            c_val, val, _ = q[idx]
            candidate = val + c_val
            if candidate < min_total:
                min_total = candidate
        dp[i] = sum_c[i] + sum_d[i] + min_total
    
    print(dp[N])

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