Submatrix

Miruna a găsit pe fundul mării o matrice cu N linii şi M coloane având elementele numere naturale. Din motive necunoscute, Mirunel, prietenul misterios al Mirunei, vrea să afle care este latura celei mai mari submatrice pătratice care conţine maxim K numere distincte. Submatricea cu colţul stânga-sus (xs, ys) şi colţul dreapta-jos (xd, yd) este formată din toate elementele din matrice având indicele liniei în intervalul [xs, xd] şi indicele coloanei în intervalul [ys, yd].

Cerinţă

Scrieţi un program care să determine latura maximă a unei submatrice care respectă condiţiile lui Mirunel.

Date de intrare

Fişierul de intrare submatrix.in conţine pe prima linie trei numere naturale N, M şi K separate prin câte un singur spaţiu având semnificaţia din enunţ. Pe următoarele N linii se găsesc câte M numere naturale separate prin spaţiu, reprezentând elementele matricei.

Date de ieşire

Fişierul de ieşire submatrix.out va conţine o singură linie pe care va fi scris un singur număr natural, reprezentând latura unei submatrice cu proprietatea din enunţ.

Restricţii

• 1 ≤ N, M ≤ 300
• 1 ≤ K ≤ N * M
• Pentru 30% din teste 1 ≤ N, M ≤ 30
• Pentru 70% din teste 1 ≤ N, M ≤ 150
• Numerele din fişierul de intrare se vor incadra pe 32 de biţi cu semn.

Exemplu

submatrix.in	submatrix.out
5 7 3 6 5 7 3 6 6 7 5 7 5 5 7 3 7 3 3 5 3 5 6 7 7 7 5 5 5 6 7 7 7 6 5 6 3 5	3

#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
 
#define dbg(x) cout << #x <<": " << x << "\n";
using ll = long long;
 
const string fn = "submatrix";
ifstream fin(fn + ".in");
ofstream fout(fn + ".out");
 
int n, m, k;
int a[305][305];
int dp[305][305];
 
int ans;
 
int mp[90005];
 
 
 
void solve(int x, int y) {
 
	for (int i = 0; i <= 90000; ++i)
		mp[i] = 0;
 
	int lat = 1, nrac = 0;
	for (int i = x, j = y; i <= n && j <= m; ++i, ++j) {
		for (int ii = i - lat + 1; ii <= i; ++ii) {
			if (mp[a[ii][j]]++ == 0)
				nrac++;
		}
		for (int jj = j - lat + 1; jj <= j; ++jj) {
			if (mp[a[i][jj]]++ == 0)
				nrac++;
		}
		while (nrac > k) {
			lat--;
			for (int ii = i - lat; ii <= i; ++ii) {
				if (mp[a[ii][j - lat]]-- == 1)
					nrac--;
			}
			for (int jj = j - lat; jj <= j; ++jj) {
				if (mp[a[i - lat][jj]]-- == 1)
					nrac--;
			}
		}
 
		// cout << lat << " ";
		ans = max(ans, lat);
		lat++;
 
	}
}
 
vector < pair<int, pair<int, int> > > x;
int main() {
 
	fin >> n >> m >> k;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			fin >> a[i][j], x.pb({a[i][j], {i, j}});
 
	sort(x.begin(), x.end());
	int ac = 0;
	a[x[0].second.first][x[0].second.second] = ac;
	for (int i = 1; i < (int)x.size(); ++i) {
		if (x[i].first != x[i - 1].first) ac++;
		a[x[i].second.first][x[i].second.second] = ac;
	}
 
	for (int i = 1; i <= n; ++i)
		solve(i, 1);
	for (int i = 1; i <= m; ++i)
		solve(1, i);
 
	fout << ans << '\n';
 
	return 0;
}