結果

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

ソースコード

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(lambda:1<<30) for _ in range(2)]
w=sum(W)
xi=bisect_left(X,S)
l=xi-1
r=xi
if l>=0:dp[1][(l-1,r,X[l],w-W[l])]=w*abs(S-X[l])
if r<N:dp[1][(l,r+1,X[r],w-W[r])]=w*abs(S-X[r])
if N==1:exit(print(min(dp[1].values())))
i=0
done=0
while not done:
    done=1
    for (l,r,p,w),v in dp[1-i].items():
        if l>=0 and p>X[l]:
            nxt=(l-1,r,X[l],w-W[l])
            dp[i][nxt]=min(dp[i][nxt],v+w*abs(p-X[l]))
            if w-W[l]>0:done=0
        if r<N and p<X[r]:
            nxt=(l,r+1,X[r],w-W[r])
            dp[i][nxt]=min(dp[i][nxt],v+w*abs(p-X[r]))
            if w-W[l]>0:done=0
    dp[1-i]=defaultdict(lambda:1<<30)
    i=1-i
print(min(dp[1-i].values()))
0