Submission #1141808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141808		Muhammet	Maxcomp (info1cup18_maxcomp)	C++20	0 / 100	1095 ms	504 KiB

maxcomp

#include "bits/stdc++.h"

using namespace std;

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

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

ll 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;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40