結果

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

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

INF = 10**18

def solve():
    n, s = map(int, input().split())
    x = list(map(int, input().split()))
    w = list(map(int, input().split()))

    # 重みを位置で管理
    buc = [0] * (10**6 + 1)
    total = 0
    for xi, wi in zip(x, w):
        buc[xi] = wi
        total += wi
        assert xi != s

    left = []
    right = []
    for xi in x:
        if xi < s:
            left.append(xi)
        else:
            right.append(xi)

    right.reverse()

    L = len(left)
    R = len(right)

    # imos
    imos_L = [0] * (L + 1)
    imos_R = [0] * (R + 1)

    for i in range(L):
        imos_L[i + 1] = imos_L[i] + buc[left[i]]
    for i in range(R):
        imos_R[i + 1] = imos_R[i] + buc[right[i]]

    # dp[i][j][side]
    dp = [[[INF, INF] for _ in range(R + 1)] for __ in range(L + 1)]

    if L:
        dp[1][0][0] = 0
    if R:
        dp[0][1][1] = 0

    for i in range(L + 1):
        for j in range(R + 1):
            for side in (0, 1):
                cur = dp[i][j][side]
                if cur == INF:
                    continue

                weight = imos_L[i] + imos_R[j]

                if side == 0:
                    pos = left[i - 1]
                else:
                    pos = right[j - 1]

                if i < L:
                    dist = abs(pos - left[i])
                    v = cur + weight * dist
                    if v < dp[i + 1][j][0]:
                        dp[i + 1][j][0] = v

                if j < R:
                    dist = abs(pos - right[j])
                    v = cur + weight * dist
                    if v < dp[i][j + 1][1]:
                        dp[i][j + 1][1] = v

    ans = INF
    if L:
        ans = min(ans, dp[L][R][0] + total * abs(s - left[-1]))
    if R:
        ans = min(ans, dp[L][R][1] + total * abs(s - right[-1]))

    print(ans)


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