No.2332 Make a Sequence
レベル :
/ AI推定難易度 : 2225
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 32
作問者 :
dyktr_06
/ テスター :
firiexp
phocom
hikikomori
sepa38
Seed57_cash
タグ : / 解いたユーザー数 32
作問者 :
hikikomori
sepa38
Seed57_cash
問題文最終更新日: 2023-05-26 23:09:17
English (AI translation)
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
MMA Contest 015
(順位表)
の他の問題:
Problem Statement
You are given an integer sequence $A$ of length $N$ and integer sequences $B, C$ of length $M$.
There is also an empty sequence $S$, and you may perform the following operation until the length of the sequence becomes $M$.
- Let $l$ be the length of the sequence $S$ before the operation. Choose an integer $k$ satisfying $1 \leq k \leq \min(M - l, N)$, and append the contiguous subarray $(A_1, A_2, …, A_k)$ to the end of the sequence $S$. This operation costs $k \times C_l$.
Determine whether the sequence $S$ can be made equal to the sequence $B$ after the operations, and if it is possible, find the minimum cost.
Constraints
- $1 \leq N, M \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$
- $1 \leq B_i \leq 10^9$
- $1 \leq C_i \leq 10^9$
- All input values are integers.
Input
The input is given from standard input in the following format.
$N$ $M$
$A_1$ $A_2$ ... $A_N$
$B_1$ $B_2$ ... $B_M$
$C_0$ $C_1$ ... $C_{M - 1}$
Output
Print on one line the minimum cost to make the sequence $S$ equal to the sequence $B$.
If it is impossible to make them equal, print $-1$.
Sample
Sample 1
Input
4 7 1 2 3 1 1 1 2 3 1 1 2 1 2 3 2 1 2 3
Output
12
For example, performing the operations in the following order is optimal.
- Append $(1)$ to the sequence $S$. This costs $1 \times 1 = 1$.
- Append $(1, 2, 3)$ to the sequence $S$. This costs $3 \times 2 = 6$.
- Append $(1)$ to the sequence $S$. This costs $1 \times 1 = 1$.
- Append $(1, 2)$ to the sequence $S$. This costs $2 \times 2 = 4$.
Sample 2
Input
3 4 1 3 2 1 3 1 2 1 1 1 1
Output
-1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。