No.2566 Beautiful Integer Sequence
タグ : / 解いたユーザー数 98
作問者 : 👑
Kyo_s_s
kusirakusira
Magentor
DeltaStruct
👑
ragna
けんぴん
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もしくは右上の雲マークをクリックしてアカウントを作成してください。