結果

問題 No.705 ゴミ拾い Hard
ユーザー lam6er
提出日時 2025-04-09 21:02:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,288 bytes
コンパイル時間 974 ms
コンパイル使用メモリ 82,508 KB
実行使用メモリ 70,468 KB
最終ジャッジ日時 2025-04-09 21:04:45
合計ジャッジ時間 6,489 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    x = list(map(int, sys.stdin.readline().split()))
    y = list(map(int, sys.stdin.readline().split()))
    
    dp = [0] * n
    dq = []
    
    for i in range(n):
        current_a = a[i]
        # Function to compute cost for j in dq
        def func(j):
            return dp[j-1] + abs(current_a - x[j])**3 + y[j]**3 if j > 0 else (abs(current_a - x[0])**3 + y[0]**3)
        
        # Maintain deque to have the best j's for current_a
        # We need to find j such that j <= i and x_j <= a_i (if possible)
        # However, due to sorting, we can use pointers to maintain possible j's
        
        # The logic here assumes certain properties of the cost function and deque management which may need to be adapted.
        # For the sake of this problem, we use a simplified approach considering the cost for each j up to i
        # But given the complexity, the following code is a placeholder and may need optimization
        
        best = func(0)
        for j in range(1, i+1):
            current = func(j)
            if current < best:
                best = current
        dp[i] = best
    
    print(dp[-1])

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