問題一覧 > 通常問題

No.2566 美しい整数列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 96
作問者 : 👑 AngrySadEightAngrySadEight / テスター : deuteridayodeuteridayo Kyo_s_sKyo_s_s kusirakusirakusirakusira MagentorMagentor DeltaStructDeltaStruct loop0919loop0919 ragnaragna マベマス（mavemas_413）マベマス（mavemas_413） けんぴんけんぴん akiaki
5 ProblemId : 9348 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-11-30 18:46:04

問題文

長さ $N$ の整数列 $A = (A_0, A_1, \dots, A_{N-1})$ と，長さ $M$ の整数列 $B = (B_0, B_1, \dots, B_{M-1})$ が与えられます．

整数列 $A$ が次の条件を満たしているとき，整数列 $A$ は美しいと言います．

  • すべての $i \ (0 \leq i \leq N - 2)$ に対して，$A_{i+1} - A_i = B_{i \bmod{M}}$．

整数列 $A$ に対して，次に示す操作を $0$ 回以上の何回でも行うことができます．

  • 整数 $x$ と，$0 \leq i \leq N - 1$ なる整数 $i$ をそれぞれ一つずつ選び，$A_i$ の値を $x$ に変える．この操作には，コストが $C_i$ かかる．

$A$ を美しい整数列にするのに必要なコストの最小値を求めてください．

制約

  • 入力はすべて整数である．
  • $1 \leq M < N \leq 2\times 10^5$
  • $-10^9 \leq A_i \leq 10^9$
  • $-10^9 \leq B_i \leq 10^9$
  • $1 \leq C_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる．

$N$ $M$
$A_0$ $A_1$ $\dots$ $A_{N-1}$
$B_0$ $B_1$ $\dots$ $B_{M-1}$
$C_0$ $C_1$ $\dots$ $C_{N-1}$

出力

答えを出力せよ．

サンプル

サンプル1
入力
5 2
2 3 5 7 11
1 2
13 17 19 23 29
出力
52

次のように操作を行うのが最適です．

  • $x = 6, i = 3$ を選ぶ．これにより，$A_3$ の値は $6$ となる．
  • $x = 8, i = 4$ を選ぶ．これにより，$A_4$ の値は $8$ となる．

このとき，数列 $A$ は $A = (2, 3, 5, 6, 8)$ となっています．したがって，

  • $A_1 - A_0 = 3 - 2 = 1 = B_0$．
  • $A_2 - A_1 = 5 - 3 = 2 = B_1$．
  • $A_3 - A_2 = 6 - 5 = 1 = B_0$．
  • $A_4 - A_3 = 8 - 6 = 2 = B_1$．

となり，整数列 $A$ は美しい整数列となっています．このとき，かかるコストの値は $C_3 + C_4 = 23 + 29 = 52$ で，これが最小です．

サンプル2
入力
3 1
1 2 3
1
1000000000 1000000000 1000000000
出力
0

操作を行う必要がありません．

サンプル3
入力
13 9
6 7 8 9 10 11 12 13 14 15 16 17 18
1 2 1 -2 3 3 4 -5 2
3 1 4 1 5 9 2 6 5 3 5 8 9
出力
39

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