問題一覧 > 通常問題

No.3417 Tired Santa

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 37
作問者 : hibit_at / テスター : shinchan
お気に入りにしたユーザー ProblemId : 12932 / 自分の提出
問題文最終更新日: 2025-12-24 10:01:50
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2025 (順位表) の他の問題:

Problem Statement

There are $N$ houses lined up on a number line, each waiting for its own dedicated present.

You are Santa. Initially, you are at position $S$ on the number line, carrying $N$ presents.

The $i$-th house is located at $X_i$ on the number line; these positions are pairwise distinct (and also different from $S$).

The $i$-th house is waiting for the $i$-th present, whose weight is $W_i$.

You must deliver the correct present to every house, but each time you move $1$ along the number line, you gain fatigue equal to the total weight of the presents you are carrying at that time.

You can hand over each present upon arriving at its corresponding house, after which you no longer need to carry that present.

When you act so as to minimize the accumulated fatigue at the moment you hand over the last present, output that minimum value.

Input

$N\ S$
$X_1 X_2 \cdots X_N$
$W_1 W_2 \cdots W_N$

  • All inputs are integers.
  • $1 \leq N \leq 10^3$
  • $1 \leq S \leq 10^6$
  • $1 \leq X_i,W_i \leq 10^6$
  • $X_1 < X_2 < \cdots < X_N$ and $X_i \neq S$

Output

Output an integer.

Sample

Sample 1
Input
2 5
2 7
10 20
Output
110

The following procedure is optimal.

  • Initially, the total weight of the presents being carried is $30$, and the accumulated fatigue is $0$.
  • Move $2$ along the number line and visit house $2$ (gaining fatigue $30 \times 2 = 60$).
  • Hand over present $2$; the total weight being carried becomes $10$.
  • Move $5$ along the number line and visit house $1$ (gaining fatigue $10 \times 5 = 50$).
  • The final accumulated fatigue is $60+50=110$.
  • If you visit house $1$ first, the accumulated fatigue is $30 \times 3 + 20 \times 5 = 190$, so the procedure above is optimal.

    Sample 2
    Input
    4 4
    1 3 5 7
    1 100 1000 10
    Output
    1383

    It is better to deliver the heavy presents first, even if it means going back and forth repeatedly.

    Sample 3
    Input
    7 5
    1 2 3 4 6 7 8
    3 1 4 1 5 2 9
    Output
    114

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。