Submission #1141811

#TimeUsernameProblemLanguageResultExecution timeMemory
1141811MuhammetMaxcomp (info1cup18_maxcomp)C++20
0 / 100
1095 ms508 KiB
#include "bits/stdc++.h"

using namespace std;

#define SZ(s) (int)s.size()
#define ff first
#define ss second
#define int long long

const int N = 1e3 + 5;
const int M = 998244353;

int T, n, m, a[N][N], mp1[N][N],  b[N], vis[N][N], ans, mn, mx, sz;

pair<int,int> mp[N];

void dfs(int x){
	int c = mp[x].ff, d = mp[x].ss;
	mn = min(mn, a[c][d]);
	mx = max(mx, a[c][d]);
	sz++;
	vis[c][d] = 1;
	if(c > 1 and !vis[c-1][d] and b[mp1[c-1][d]]) dfs(mp1[c-1][d]);
	if(d > 1 and !vis[c][d-1] and b[mp1[c][d-1]]) dfs(mp1[c][d-1]);
	if(c < n and !vis[c+1][d] and b[mp1[c+1][d]]) dfs(mp1[c+1][d]);
	if(d < m and !vis[c][d+1] and b[mp1[c][d+1]]) dfs(mp1[c][d+1]);
}

void f(int x){
	if(x == n*m+1){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				vis[i][j] = 0;
			}
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				if(!vis[i][j] and b[mp1[i][j]]){
					sz = mx = 0;
					mn = 1e9;
					dfs(mp1[i][j]);
					ans = max(ans, mx-mn-sz);
				}
			}
		}
		return;
	}
	b[x] = 1;
	f(x+1);
	b[x] = 0;
	f(x+1);
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> m;
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
			mp[++cnt] =  {i,j};
			mp1[i][j] = cnt;
		}
	}
	f(1);
	cout << ans << '\n';

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...