問題一覧 > 通常問題

No.2566 美しい整数列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 98
作問者 : 👑 AngrySadEight / テスター : deuteridayo Kyo_s_s kusirakusira Magentor DeltaStruct 👑 loop0919 ragna マベマス（mavemas_413） けんぴん aki
5 ProblemId : 9348 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-11-30 18:46:04

問題文

長さ NN の整数列 A=(A0,A1,…,AN−1)A = (A_0, A_1, \dots, A_{N-1}) と，長さ MM の整数列 B=(B0,B1,…,BM−1)B = (B_0, B_1, \dots, B_{M-1}) が与えられます．

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

  • すべての i (0≤i≤N−2)i \ (0 \leq i \leq N - 2) に対して，Ai+1−Ai=Bi mod MA_{i+1} - A_i = B_{i \bmod{M}}．

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

  • 整数 xx と，0≤i≤N−10 \leq i \leq N - 1 なる整数 ii をそれぞれ一つずつ選び，AiA_i の値を xx に変える．この操作には，コストが CiC_i かかる．

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

制約

  • 入力はすべて整数である．
  • 1≤M<N≤2×1051 \leq M < N \leq 2\times 10^5
  • −109≤Ai≤109-10^9 \leq A_i \leq 10^9
  • −109≤Bi≤109-10^9 \leq B_i \leq 10^9
  • 1≤Ci≤1091 \leq C_i \leq 10^9

入力

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

NN MM
A0A_0 A1A_1 …\dots AN−1A_{N-1}
B0B_0 B1B_1 …\dots BM−1B_{M-1}
C0C_0 C1C_1 …\dots CN−1C_{N-1}

出力

答えを出力せよ．

サンプル

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

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

  • x=6,i=3x = 6, i = 3 を選ぶ．これにより，A3A_3 の値は 66 となる．
  • x=8,i=4x = 8, i = 4 を選ぶ．これにより，A4A_4 の値は 88 となる．

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

  • A1−A0=3−2=1=B0A_1 - A_0 = 3 - 2 = 1 = B_0．
  • A2−A1=5−3=2=B1A_2 - A_1 = 5 - 3 = 2 = B_1．
  • A3−A2=6−5=1=B0A_3 - A_2 = 6 - 5 = 1 = B_0．
  • A4−A3=8−6=2=B1A_4 - A_3 = 8 - 6 = 2 = B_1．

となり，整数列 AA は美しい整数列となっています．このとき，かかるコストの値は C3+C4=23+29=52C_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もしくは右上の雲マークをクリックしてアカウントを作成してください。