시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 39 19 15 46.875%

문제

JOI 高校の生徒である葵はデジタルアート制作が趣味であり,今日も新しい画像を作った.

この画像のサイズは,縦 H ピクセル,横 W ピクセルであり,H × W のマス目のような形で表される.ここで,上から i 行目 (1 ≦ i ≦ H),左から j 列目 (1 ≦ j ≦ W) のピクセルを (i, j) で表す.各ピクセルは 1 つの色で塗られている.各色には 1 から 256 までの番号が付けられており,ピクセル (i, j) の色の番号は Ai, j である.

葵はこの画像を同級生である凛に見せたが,凛は「画像に使われている色の種類が多すぎる」という理由で気に入らなかった.そこで葵は,以下のように画像内のある領域を隠して,見える色の種類をできるだけ少なくできないかと考えた.

  • 葵は S 個以下のピクセルを選んで隠す.
  • ただし,隠すピクセルの領域は 1 つの長方形で表されなければならない.

画像のデータと,隠すピクセルの個数の上限 S が与えられたとき,画像内のある領域を隠したときに見える色の種類の数としてありうる最小の値を求めるプログラムを作成せよ.

입력

入力は以下の形式で標準入力から与えられる.

H W S
A1, 1   A1, 2      A1, W
A2, 1   A2, 2      A2, W
:
AH, 1   AH, 2      AH, W

출력

標準出力に,画像内のある領域を隠したときに見える色の種類の数としてありうる最小の値を 1 行で出力せよ.

特に,見えるピクセルが一つもない状態にできる場合は 0 と出力せよ.

제한

  • 1 ≦ H ≦ 1 000
  • 1 ≦ W ≦ 1 000
  • 1 ≦ S ≦ HW
  • 1 ≦ Ai, j ≦ 256 (1 ≦ i ≦ H1 ≦ j ≦ W).
  • 入力される値はすべて整数である.

서브태스크

번호 배점 제한
1 8

H = 1W ≦ 10

2 10

H ≦ 10W ≦ 10

3 5

S = 1

4 6

Ai, j ≦ 2 (1 ≦ i ≦ H1 ≦ j ≦ W).

5 5

Ai, j ≦ 4 (1 ≦ i ≦ H1 ≦ j ≦ W).

6 13

Ai, j ≦ 15 (1 ≦ i ≦ H1 ≦ j ≦ W).

7 13

Ai, j ≦ 30 (1 ≦ i ≦ H1 ≦ j ≦ W).

8 15

Ai, j ≦ 70 (1 ≦ i ≦ H1 ≦ j ≦ W).

9 25

追加の制約はない.

예제 입력 1

1 10 7
5 1 2 5 2 2 5 6 6 5

예제 출력 1

2

例えば,左から数えて 2 番目から 8 番目までのピクセルを隠すと,番号 5, 6 の色だけが見え,その種類の数は 2 となる.この場合,隠すピクセルは 7 個となり,条件を満たす.また,葵は見える色を 1 種類以下にすることはできない.よって 2 を出力する.

この入力例は小課題 1, 2, 6, 7, 8, 9 の制約を満たす.

예제 입력 2

10 10 45
1 1 1 1 1 1 1 1 1 1
1 1 1 2 2 3 3 1 1 1
1 1 2 1 2 3 1 3 1 1
1 2 1 2 6 6 3 1 3 1
1 2 2 6 1 1 6 3 3 1
1 4 4 6 1 1 6 5 5 1
1 4 1 4 6 6 5 1 5 1
1 1 4 1 4 5 1 5 1 1
1 1 1 4 4 5 5 1 1 1
1 1 1 1 1 1 1 1 1 1

예제 출력 2

4

例えば,左上をピクセル (2, 1),右下をピクセル (7, 7) とする長方形領域を隠すと,番号 1, 3, 4, 5 の色だけが見え,その種類の数は 4 となる.この場合,隠すピクセルは 42 個となり,条件を満たす.

この説明を図で表すと,以下のようになる.

この入力例は小課題 2, 6, 7, 8, 9 の制約を満たす.

예제 입력 3

5 10 1
2 3 5 7 1 1 1 3 1 7
1 9 2 3 2 9 3 1 3 7
4 1 4 3 4 7 5 3 5 9
6 1 6 7 7 1 7 3 7 9
8 3 8 9 9 7 2 3 5 7

예제 출력 3

9

隠すピクセルを S = 1 個以下にするという条件の下では,葵は番号 1, 2, 3, ..., 9 の 9 種類の色が見えるようにしかできない.よって 9 を出力する.

この入力例は小課題 2, 3, 6, 7, 8, 9 の制約を満たす.

예제 입력 4

9 6 54
1 1 1 1 1 3
6 14 14 3 3 12
9 13 1 10 3 3
9 13 5 5 3 3
6 13 10 3 7 3
2 5 8 5 3 3
6 5 5 3 15 3
6 5 10 5 3 3
2 2 5 7 3 3

예제 출력 4

0

54 個すべてのピクセルを隠して,見えるピクセルが一つもないようにできる.よって 0 を出力する.

この入力例は小課題 2, 6, 7, 8, 9 の制約を満たす.

예제 입력 5

8 10 59
3 3 3 3 3 3 3 3 2 3
3 1 3 3 3 3 3 2 3 3
3 3 1 4 3 4 2 3 3 3
3 3 3 1 4 2 4 3 3 3
3 3 3 4 1 4 2 3 3 3
3 3 3 1 4 3 4 2 3 3
3 3 1 3 3 3 3 3 2 3
3 1 3 3 3 3 3 3 3 3

예제 출력 5

2

例えば,左上をピクセル (3, 1),右下をピクセル (10, 7) とする長方形領域を隠すと,番号 1, 3 の色だけが見え,その種類の数は 2 となる.この場合,隠すピクセルは 56 個となり,条件を満たす.

この説明を図で表すと,以下のようになる.

この入力例は小課題 2, 5, 6, 7, 8, 9 の制約を満たす.

채점 및 기타 정보

  • 예제는 채점하지 않는다.