結果

問題 No.3417 Tired Santa
コンテスト
ユーザー tkykwtnb
提出日時 2025-12-28 08:39:59
言語 PyPy3
(7.3.17)
結果
WA  
実行時間 -
コード長 842 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 497 ms
コンパイル使用メモリ 82,156 KB
実行使用メモリ 84,872 KB
最終ジャッジ日時 2025-12-28 08:40:06
合計ジャッジ時間 5,669 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
i=0
if l>=0:dp[i][(l-1,r,X[l],w-W[l])]=w*abs(S-X[l])
if r<N:dp[i][(l,r+1,X[r],w-W[r])]=w*abs(S-X[r])
done=0
while not done:
    done=1
    i=1-i
    dp[i]=defaultdict(lambda:1<<30)
    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
if dp[i]:print(min(dp[i].values()))
else:print(min(dp[1-i].values()))
0