Submission #1149315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149315		adlin	Maxcomp (info1cup18_maxcomp)	C++20	60 / 100	108 ms	8264 KiB

maxcomp

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define F first
#define S second
#define all(v) (v).begin(),(v).end()
#define ull unsigned long long
#define ahahahant ios_base::sync_with_stdio(0);cin.tie(0); 
#define int long long

using namespace std;

//mt19937 rng( chrono::steady_clock::now().time_since_epoch().count());
// 
//ll rand( ll l, ll r )
//{
//    uniform_int_distribution <ll> uid( l, r );
//    return uid( rng );
//}

ll lcm(ll x, ll y){
	return x / __gcd(x,y) * y;
}

ll binpow(ll a, ll b, ll m){
	if(!b) return 1ll;
	if(b & 1) return binpow(a,b-1,m) * a % m;
	int res = binpow(a,b/2,m) % m;
	return res * res % m;
}

const int maxn = 1e6 + 6;

const int mod = 1e9 + 7;

const int mod2 = 998244353;

const ll inf = 1e18;

const int inf2 = 1e9;

const int K = 300;

int n,m,a[1005][1005],c[1005][1005],timer;

bool used[1005][1005];

pair <int,int> rev[maxn];

int cnt, mxx, mnn;

void dfs(int x, int y){
	cnt++;
	used[x][y] = 1;
	mxx = max(mxx, a[x][y]);
	mnn = min(mnn, a[x][y]);
	if(x + 1 <= n && !used[x + 1][y]) dfs(x + 1,y);
	if(x - 1 >= 1 && !used[x - 1][y]) dfs(x - 1,y);
	if(y + 1 <= m && !used[x][y + 1]) dfs(x,y + 1);
	if(y - 1 >= 1 && !used[x][y - 1]) dfs(x,y - 1);
}

void who(){
	
	cin >> n >> m;
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	
	if(n == 1){
		int ans = -1;
		for(int i = 1; i <= m; i++){
			int mx = 0, mn = 1e9, sz = 0;
			for(int j = i; j <= m; j++){
				mx = max(mx, a[1][j]);
				mn = min(mn, a[1][j]);
				sz++;
				ans = max(ans, mx - mn - sz);
			}
		}
		cout << ans;
	}
	else if(n * m <= 20){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				c[i][j] = timer++;
				rev[c[i][j]] = {i,j};
			}
		}
		
		int ans = -1;
		
		for(int mask = 0; mask < (1 << (n * m)) - 1; mask++){
			pair <int,int> s;
			for(int i = 1; i <= n; i++){
				for(int j = 1; j <= m; j++){
					if(mask & (1 << c[i][j])){
						used[i][j] = 1;
					}
					else {
						s.F = i;
						s.S = j;
					}
				}
			}
			cnt = 0;
			mxx = 0;
			mnn = 1e9;
			dfs(s.F,s.S);
			ans = max(ans, mxx - mnn - cnt);
			for(int i = 1; i <= n; i++){
				for(int j = 1; j <= m; j++){
					used[i][j] = 0;
				}
			}
		}
		
		cout << ans << '\n';	
	}
	else if(n <= 50 && m <= 50){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				c[i][j] = timer++;
				rev[c[i][j]] = {i,j};
			}
		}
		
		vector <int> v1,v2;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				v1.pb(c[i][j]);
				v2.pb(c[i][j]);
			}
		}
		
		int ans = -1;
		
		for(int i = 0; i < v1.size(); i++){
			for(int j = 0; j < v2.size(); j++){
				int x1,x2,y1,y2;
				x1 = rev[v1[i]].F;
				y1 = rev[v1[i]].S;
				x2 = rev[v2[j]].F;
				y2 = rev[v2[j]].S;
				ans = max(ans, a[x1][y1] - a[x2][y2] - (abs(x1-x2)+abs(y1-y2)) - 1);
			}
		}
		
		cout << ans;
		
	}
	
}

signed main(){
	
//	freopen("yinyang.in", "r", stdin);
//	freopen("yinyang.out", "w", stdout);
	
	ahahahant
		
	int tt = 1;
	
//	cin >> tt;
	
	while(tt--){
		who();
	}
	
	
	return 0;
}

/*
__builtin_popcount
__builtin_clz
__builtin_ctz
__builtin_parity
int get(int r){
	int res = 0;
	for(; r >= 0; r = (r & (r + 1)) - 1) res += f[r];
	return res;
}
 
void upd(int i, int val){
	for(; i <= n; i = (i | (i + 1))) f[i] += val;
}
*/ 	

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