問題一覧 > 通常問題

No.2006 Decrease All to Zero

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : to-omerto-omer / テスター : chineristACchineristAC 👑 ygussanyygussany
3 ProblemId : 7758 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-05 22:15:04

問題文

$1$ から $N$ までの番号の付いたボタンと長さ $N$ の正整数列 $A$ があります。
ボタン $i$ は数直線上の座標 $X_i$ にあり、ボタン $i$ を $1$ 回押すことで $A_i$ を $1$ 小さくすることができます。
ただし、同じボタンを連続で押すことができなくなっています。より正確には、ボタン $B_1,B_2,\dots,B_K$ をこの順に押した時、 $1\le j\le K-1$ を満たすすべての $j$ で $B_j\neq B_{j+1}$ を満たす必要があります。
$A$ の全ての要素を $0$ にすることが可能かどうか判定し、可能な場合は最初にボタンを押してから最後にボタンを押すまでの数直線上の移動距離の最小値を求めてください。

制約

  • 入力は全て整数である。
  • $1\le N\le 200$
  • $1\le X_1<X_2<\dots<X_N\le 10^{9}$
  • $1\le A_i\le 5000\ (1\le i\le N)$

入力

$N$
$X_1$ $X_2$ $\dots$ $X_N$
$A_1$ $A_2$ $\dots$ $A_N$

出力

$A$ の全ての要素を $0$ にすることが不可能な場合 $-1$ を出力してください。可能な場合は移動距離の最小値を出力してください。

サンプル

サンプル1
入力
3
1 2 3
1 2 1
出力
3

$1\to 2\to 3\to 2$ の順にボタンを押すことで移動距離 $3$ で $A$ の全ての要素を $0$ にすることができます。
$1\to 2\to 2\to 3$ の順にボタンを押せないことに注意してください。

サンプル2
入力
2
1 2
1 3
出力
-1
サンプル3
入力
10
2 3 5 7 11 13 17 19 23 29
5000 5000 5000 5000 5000 5000 5000 5000 5000 5000
出力
130001

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