問題一覧 > 通常問題

No.2114 01 Matching

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 : bayashikobayashiko / テスター : first_vilfirst_vil noiminoimi
1 ProblemId : 8613 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-28 17:07:39

問題文

$N$ 個の青い頂点と $M$ 個の赤い頂点からなる、 $N+M$ 頂点のグラフ $G$ があります。はじめ、グラフ $G$ に辺は存在しません。

各頂点には整数が書かれており、$i$ $(1\leq i \leq N)$ 個目の青い頂点に書かれている整数は $B_i$ で、 $j$ $(1 \leq j \leq M)$ 個目の赤い頂点に書かれている整数は $R_j$ です。

まず、あなたは以下の操作 $1$ を何回でも行うことが出来ます。

  • コストを $1$ 支払い、 $G$ の $N+M$ 個の頂点のうち $1$ つを選び、その頂点に書かれている整数の値を $K$ 増やす。

その後、あなたは以下の操作 $2$ を何回でも行うことが出来ます。

  • ともに次数が $0$ で、書かれている整数が等しい青い頂点と赤い頂点を $1$ つずつ選び、それらの間に無向辺を $1$ 本追加する。

あなたの目標は、 $G$ に含まれる辺の本数を $\min(N,M)$ 本にすることです。

目標が達成可能であるか判定し、達成可能ならば目標を達成するために支払う必要のあるコストの総和の最小値を求めてください。

入力

$N\ M\ K$
$B_1\ B_2\ \ldots\ B_N$
$R_1\ R_2\ \ldots\ R_M$

  • $1\le N,M\le 2×10^5$
  • $1\le K\le 10^9$
  • $0\le B_i,R_i\le 10^9$
  • 入力はすべて整数

出力

目標が達成可能である場合、目標を達成するのに支払う必要のあるコストの総和の最小値を出力してください。

どのように操作を行っても目標の達成が不可能である場合、 -1 と出力してください。

サンプル

サンプル1
入力
2 3 1
4 5
2 3 6
出力
2

例えば以下のように操作 $1$ を行うと良いです。

  • コストを $1$ 支払い、$2$ 個目の青い頂点に書かれている整数を $1$ 増やす。
  • コストを $1$ 支払い、$2$ 個目の赤い頂点に書かれている整数を $1$ 増やす。

操作 $1$ を終えた時点で、 $B_1=4,B_2=6,R_1=2,R_2=4,R_3=6$ となっています。

操作 $2$ は以下のように行うと良いです。

  • $1$ 個目の青い頂点と $2$ 個目の赤い頂点の間に無向辺を追加する。
  • $2$ 個目の青い頂点と $3$ 個目の赤い頂点の間に無向辺を追加する。

このように操作 $1$ および操作 $2$ を行うと、 合計 $2$ のコストで $G$ に含まれる辺の本数を $\min(2,3)=2$ 本にすることが出来ます。

$1$ 以下のコストで目標を達成する方法はないため、 $2$ が答えです。

サンプル2
入力
1 1 2
0
1
出力
-1

どのように操作を行っても目標を達成することは出来ません。

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