結果

問題 No.3417 Tired Santa
コンテスト
ユーザー LyricalMaestro
提出日時 2026-01-01 17:14:33
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 405 ms / 2,000 ms
コード長 3,160 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 502 ms
コンパイル使用メモリ 82,080 KB
実行使用メモリ 172,388 KB
最終ジャッジ日時 2026-01-01 17:14:40
合計ジャッジ時間 6,424 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/3417

from collections import deque

MAX_INT = 10 ** 18

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

    s_index = 0
    array = []
    s_added = False
    for i in range(N):
        if X[i] > S and not s_added:
            array.append((-1, S, 0))
            s_index = len(array) - 1
            s_added = True

        array.append((i, X[i], W[i]))
    if not s_added:
        array.append((-1, S, 0))
        s_index = len(array) - 1
        s_added = True

    # [left, right]までにまで運んだのちに残るweightを計算
    weights = [[0] * len(array) for _ in range(len(array))]
    total = sum(W)
    for left in reversed(range(s_index + 1)):
        total -= array[left][2]
        t = total
        for right in range(s_index, len(array)):
            if s_index < right:
                t -= array[right][2]
            weights[left][right] = t

    # 
    dp = [[[MAX_INT, MAX_INT] for _ in range(len(array))] for _ in range(len(array))]
    dp[s_index][s_index][0] = 0
    for length in range(1, len(array) + 1):
        for left_index in range(len(array)):
            right_index = left_index + length - 1

            if right_index >= len(array):
                break

            for state in range(2):
                if dp[left_index][right_index][state] == MAX_INT:
                    continue

                # 左に拡張する                
                if left_index > 0:
                    if state == 0:
                        cost = dp[left_index][right_index][state]
                        new_cost = cost + weights[left_index][right_index] * (abs(array[left_index - 1][1] - array[left_index][1]))
                        dp[left_index - 1][right_index][0] = min(dp[left_index - 1][right_index][0], new_cost)
                    else:
                        # state == 1
                        cost = dp[left_index][right_index][state]
                        new_cost = cost + weights[left_index][right_index] * (abs(array[left_index - 1][1] - array[right_index][1]))
                        dp[left_index - 1][right_index][0] = min(dp[left_index - 1][right_index][0], new_cost)

                # 右に拡張する                
                if right_index < len(array) - 1:
                    if state == 0:
                        cost = dp[left_index][right_index][state]
                        new_cost = cost + weights[left_index][right_index] * (abs(array[right_index + 1][1] - array[left_index][1]))
                        dp[left_index][right_index + 1][1] = min(dp[left_index][right_index + 1][1], new_cost)
                    else:
                        # state == 1
                        cost = dp[left_index][right_index][state]
                        new_cost = cost + weights[left_index][right_index] * (abs(array[right_index + 1][1] - array[right_index][1]))
                        dp[left_index][right_index + 1][1] = min(dp[left_index][right_index + 1][1], new_cost)


    print(min(dp[0][-1]))



        




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