問題一覧 > 通常問題

No.2157 崖

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 89
作問者 : keisuke6keisuke6 / テスター : hibit_athibit_at KowerKoint2010KowerKoint2010 kotamanegikotamanegi
1 ProblemId : 8898 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-08 23:04:02

問題文

毎朝開催されるバーチャルコンテスト「あさかつ」では $N$ 問の問題がそれぞれ決まった難易度帯から出題されます.

隣り合う問題の難易度の差は と呼ばれ、一般的に崖が大きいことはあまり好まれません.

なので、問題を選定する時は崖を小さくすることが望ましいです.

次の問いは、これを一般化したものです.

$N$ 種類の難易度帯 $D_i$ に含まれる問題はそれぞれ $M$ 問あり、$D_{i,j}$ として与えられます.

これを用いて、問題のセット $A$ の各要素を次のように定義します.

  • $A_i(1\leq{i}\leq{N})$ を難易度帯 $D_i$ の問題の中から一つ選ぶ.

ただし、 $A$ は広義単調増加列でなければなりません.

つまり、任意の $1 \leq i \leq N-1$ に対して $A_i \leq A_{i+1}$ が成り立つ必要があります.

このとき、$A$ に対して $f(A)$ を「各 $i$ に対する $A_{i+1}-A_i$ の最大値」で定めたとき、$f(A)$ の最小値を解答してください.

ただし、条件を満たす $A$ が存在しない場合は -1 を出力してください.

入力

$N\ M$ 
$D_{1,1} , D_{1,2} , \cdots , D_{1,M}$
$D_{2,1} , D_{2,2} , \cdots , D_{2,M}$
$\hspace{8pt}\vdots \hspace{19pt} \vdots \hspace{9pt}\ddots \hspace{11pt}\vdots$
$D_{N,1} , D_{N,2} , \cdots , D_{N,M}$

  • $1\leq{N,M}\leq{1500}$
  • $1\leq{D_{i,j}}\leq{10^9}$

出力

$f(A)$ の最小値を一行に出力してください.ただし,条件を満たす $A$ が存在しない場合は -1 を出力してください.

サンプル

サンプル1
入力
2 2
5 8
12 7
出力
2

$A=(5,7)$ が最適です.

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

$A=(4,4,4,4)$ が最適です.

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

条件を満たす $A$ が存在しない場合は -1 を出力してください.

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