結果

問題 No.3417 Tired Santa
コンテスト
ユーザー titia
提出日時 2025-12-24 03:27:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 303 ms / 2,000 ms
コード長 1,653 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 356 ms
コンパイル使用メモリ 82,880 KB
実行使用メモリ 96,572 KB
最終ジャッジ日時 2025-12-24 03:27:12
合計ジャッジ時間 5,100 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

N,S=map(int,input().split())
X=list(map(int,input().split()))
W=list(map(int,input().split()))

ind=N

for i in range(N):
    if X[i]>S:
        ind=i
        break

X=X[:ind]+[S]+X[ind:]
W=W[:ind]+[0]+W[ind:]

N+=1

DP=[[1<<60]*(N) for i in range(N)]
DP2=[[1<<60]*(N) for i in range(N)]
DP[ind][ind]=0
SUM=sum(W)
Q=[(ind,ind,SUM,0)]

WS=[0]
for w in W:
    WS.append(WS[-1]+w)


while Q:
    NQ=[]
    while Q:
        l,r,weight,com=Q.pop()
        
        if com==0:
            now=DP[l][r]

            if r+1<N:
                dis=X[r+1]-X[r]
                minus=W[r+1]

                if DP[l][r+1]>now+dis*weight:
                    DP[l][r+1]=now+dis*weight
                    NQ.append((l,r+1,weight-minus,0))
            if l-1>=0:
                dis=X[r]-X[l-1]
                minus=W[l-1]

                if DP2[l-1][r]>now+dis*weight:
                    DP2[l-1][r]=now+dis*weight
                    NQ.append((l-1,r,weight-minus,1))
        else:
            now=DP2[l][r]

            if r+1<N:
                dis=X[r+1]-X[l]
                minus=W[r+1]

                if DP[l][r+1]>now+dis*weight:
                    DP[l][r+1]=now+dis*weight
                    NQ.append((l,r+1,weight-minus,0))
            if l-1>=0:
                dis=X[l]-X[l-1]
                minus=W[l-1]

                if DP2[l-1][r]>now+dis*weight:
                    DP2[l-1][r]=now+dis*weight
                    NQ.append((l-1,r,weight-minus,1))

    Q=list(set(NQ))

ANS=DP[0][N-1]
ANS2=DP2[0][N-1]

print(min(ANS,ANS2))
0