問題一覧 > 通常問題

No.3417 Tired Santa

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 : hibit_at / テスター : shinchan
ProblemId : 12932 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-12-24 10:01:50
コンテストの他の問題:

問題文

数直線上に $N$ 個の家が並んでおり、それぞれ専用のプレゼントを待っています。

サンタであるあなたは、はじめ、数直線上の $S$ の位置におり、$N$ 個のプレゼントを運搬しています。

$i$ 軒目の家は、数直線上の相異なる（かつ、$S$ とも異なる）$X_i$ に位置しています。

また、$i$ 軒目の家はそれぞれ $i$ 番目のプレゼントを待っており、その重さは $W_i$ です。

あなたはすべての家に正しいプレゼントを配らなければいけませんが、数直線上を $1$ 移動する度に、そのとき運搬しているプレゼントの総重量に等しい値の疲労を得ます。

あなたは、それぞれのプレゼントに対応する家に到着した時点でそのプレゼントを渡すことができ、その後そのプレゼントを運搬する必要はなくなります。

最後のプレゼントを渡した瞬間の疲労の蓄積が最小になるように行動したとき、その最小値を出力してください。

入力

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

  • 入力はすべて整数
  • $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$ かつ $X_i \neq S$

出力

整数を出力してください。

サンプル

サンプル1
入力
2 5
2 7
10 20
出力
110

以下の手順が最適です。

  • はじめ、運搬しているプレゼントの総重量は $30$、疲労の蓄積は $0$ である
  • 数直線上を $2$ 移動し、家 $2$ を訪問をする（疲労を $30 \times 2 = 60$ 得る）
  • プレゼント $2$ を渡し、運搬している総重量は $10$ になる
  • 数直線上を $5$ 移動し、家 $1$ を訪問する（疲労を $10 \times 5 = 50$ 得る）
  • 最終的な疲労の蓄積は $60+50=110$ となる

    • 家 $1$ から訪問する場合、疲労の蓄積は $30 \times 3 + 20 \times 5 = 190$ となるので、上の手順が最適です。

    サンプル2
    入力
    4 4
1 3 5 7
1 100 1000 10
    出力
    1383

    往復を繰り返してでも重いプレゼントを先に届けた方がいいです。

    サンプル3
    入力
    7 5
1 2 3 4 6 7 8
3 1 4 1 5 2 9
    出力
    114

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