問題一覧 > 通常問題

No.1818 6 Operations

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 48
作問者 : nok0 / テスター : 👑 Forested riano
お気に入りにしたユーザー ProblemId : 7267 / 自分の提出
問題文最終更新日: 2022-01-23 11:10:06
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
yukicoder contest 328 (順位表) の他の問題:

Problem Statement

You are given a sequence $A$ of non-negative integers of length $N$ and a sequence $B$ of non-negative integers of length $M$.

You may repeat the following $6$ types of operations in any order, any number of times.

  • Choose $i\ (1 \le i \le |A|)$. Replace the value of $A_i$ with $A_i+1$.

  • Choose $i\ (1 \le i \le |A|)$. Replace the value of $A_i$ with $A_i-1$.

  • Choose $i\ (1 \le i \le |A| - 1)$. Replace the value of $A_i$ with $A_i+A_{i+1}$, and delete $A_{i+1}$.

  • Choose $i\ (1 \le i \le |A| - 1)$. Replace the value of $A_i$ with $A_i+A_{i+1}+1$, and delete $A_{i+1}$.

  • Choose $i\ (1 \le i \le |A|)$ and a non-negative integer $x$. Replace the value of $A_i$ with $A_i-x$, and insert $x$ immediately after $A_i$.

  • Choose $i\ (1 \le i \le |A|)$ and a non-negative integer $x$. Replace the value of $A_i$ with $A_i-x-1$, and insert $x$ immediately after $A_i$.

However, at every moment during the operations, all elements of the sequence $A$ must be non-negative.

Find the minimum number of operations required to make the sequence $A$ equal to the sequence $B$.

Constraints

  • All inputs are integers.
  • $1 \le N \le 10^3$
  • $1 \le M \le 10^3$
  • $0 \le A_i$
  • $0 \le B_i$
  • $\sum_{i=1}^N A_i \le 3\times 10^3$
  • $\sum_{i=1}^M B_i \le 3\times 10^3$

Input

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_M$

Output

Output the minimum number of operations required to make $A$ and $B$ equal.

Sample

Sample 1
Input
3 2
3 1 4
1 5
Output
3

Below, for convenience, the operations given in the problem statement are called operation $1$, operation $2$, $\dots$, operation $6$, from top to bottom.

By performing the operations as follows, $A$ and $B$ can be made equal in $3$ operations.

  • Choose $i=1$ in operation $2$. As a result, $A=(2,1,4)$.

  • Choose $i=1$ in operation $2$. As a result, $A=(1,1,4)$.

  • Choose $i=2$ in operation $3$. As a result, $A=(1,5)=B$.

It can be proved that it is impossible to make $A$ and $B$ equal in fewer than $3$ operations, so the answer is $3$.

Sample 2
Input
1 1
0
3000
Output
3000

Sample 3
Input
6 5
2 7 1 8 2 8
1 8 2 8 4
Output
8

By performing the operations as follows, $A$ and $B$ can be made equal in $8$ operations.

  • Choose $i=6$ in operation $2$. As a result, $A=(2,7,1,8,2,7)$.

  • Choose $i=6$ in operation $2$. As a result, $A=(2,7,1,8,2,6)$.

  • Choose $i=6$ in operation $2$. As a result, $A=(2,7,1,8,2,5)$.

  • Choose $i=6$ in operation $2$. As a result, $A=(2,7,1,8,2,4)$.

  • Choose $i=2$ in operation $3$. As a result, $A=(2,8,8,2,4)$.

  • Choose $i=1$ in operation $2$. As a result, $A=(1,8,8,2,4)$.

  • Choose $i=3,x=2$ in operation $5$. As a result, $A=(1,8,2,6,2,4)$.

  • Choose $i=4$ in operation $3$. As a result, $A=(1,8,2,8,4)=B$.

It can be proved that it is impossible to make $A$ and $B$ equal in fewer than $8$ operations, so the answer is $8$.

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