結果

問題 No.3417 Tired Santa
コンテスト
ユーザー tkykwtnb
提出日時 2025-12-28 08:17:25
言語 PyPy3
(7.3.17)
結果
RE  
実行時間 -
コード長 1,024 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,119 ms
コンパイル使用メモリ 81,964 KB
実行使用メモリ 82,228 KB
最終ジャッジ日時 2025-12-28 08:17:41
合計ジャッジ時間 5,792 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 RE * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from bisect import bisect_left
from collections import defaultdict
N,S=map(int,input().split())
X=list(map(int,input().split()))
W=list(map(int,input().split()))
dp=[defaultdict(int) for _ in range(2)]
w=sum(W)
xi=bisect_left(X,S)
l=xi-1
r=xi
dp[1][(l-1,r,X[l],w-W[l])]=w*abs(S-X[l])
dp[1][(l,r+1,X[r],w-W[r])]=w*abs(S-X[r])
i=0
done=0
while not done:
    done=1
    for (l,r,p,w),ans in dp[1-i].items():
        if l>=0 and p>X[l]:
            if (l-1,r,X[l],w-W[l]) in dp[i]:
                dp[i][(l-1,r,X[l],w-W[l])]=min(dp[i][(l-1,r,X[l],w-W[l])],ans+w*abs(p-X[l]))
            else:
                dp[i][(l-1,r,X[l],w-W[l])]=ans+w*abs(p-X[l])
            if w-W[l]>0:done=0
        if r<N and p<X[r]:
            if (l,r+1,X[r],w-W[r]) in dp[i]:
                dp[i][(l,r+1,X[r],w-W[r])]=min(dp[i][(l,r+1,X[r],w-W[r])],ans+w*abs(p-X[r]))
            else:
                dp[i][(l,r+1,X[r],w-W[r])]=ans+w*abs(p-X[r])
            if w-W[l]>0:done=0
    dp[1-i]=defaultdict(int)
    i=1-i
print(min(dp[1-i].values()))
0