問題一覧 > 通常問題

No.2566 Beautiful Integer Sequence

レベル : / AI推定難易度 : 1000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 98
作問者 : 👑 AngrySadEight / テスター : deuteridayo Kyo_s_s kusirakusira Magentor DeltaStruct 👑 loop0919 ragna マベマス(mavemas_413) けんぴん aki
お気に入りにしたユーザー ProblemId : 9348 / 自分の提出
問題文最終更新日: 2023-11-30 18:46:04
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
第2回緑以下コンテスト (順位表) の他の問題:

Problem Statement

You are given an integer sequence $A = (A_0, A_1, \dots, A_{N-1})$ of length $N$ and an integer sequence $B = (B_0, B_1, \dots, B_{M-1})$ of length $M$.

When the integer sequence $A$ satisfies the following condition, the integer sequence $A$ is said to be beautiful.

  • For all $i \ (0 \leq i \leq N - 2)$, $A_{i+1} - A_i = B_{i \bmod{M}}$.

You may perform the following operation on the integer sequence $A$ any number of times, $0$ or more.

  • Choose one integer $x$ and one integer $i$ such that $0 \leq i \leq N - 1$, and change the value of $A_i$ to $x$. This operation costs $C_i$.

Find the minimum cost required to make $A$ a beautiful integer sequence.

Constraints

  • All input values are integers.
  • $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$

Input

The input is given from standard input in the following format.

$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}$

Output

Output the answer.

Sample

Sample 1
Input
5 2
2 3 5 7 11
1 2
13 17 19 23 29
Output
52

It is optimal to perform the operations as follows.

  • Choose $x = 6, i = 3$. This makes the value of $A_3$ equal to $6$.
  • Choose $x = 8, i = 4$. This makes the value of $A_4$ equal to $8$.

At this point, the sequence $A$ is $A = (2, 3, 5, 6, 8)$. Therefore,

  • $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$.

and so the integer sequence $A$ is a beautiful integer sequence. The cost in this case is $C_3 + C_4 = 23 + 29 = 52$, which is the minimum.

Sample 2
Input
3 1
1 2 3
1
1000000000 1000000000 1000000000
Output
0

No operations need to be performed.

Sample 3
Input
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
Output
39

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