Submission #1160945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160945		Nurislam	The Kingdom of JOIOI (JOI17_joioi)	C++20	0 / 100	0 ms	320 KiB

joioi

#include <bits/stdc++.h>

using namespace std;


#define int long long
#define pb push_back

int inf = 2e9;

void solve(){
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int> (m));
	
	array<int,3> mx = {0, 0, 0}, mn = {inf, 0, 0};
	for(int i = 0; i < n; i ++ )
		for(int j = 0; j < m; j ++ ){
			cin >> a[i][j];
			if(mx[0] <= a[i][j]) mx = {a[i][j], i, j};
			if(mn[0] >= a[i][j]) mn = {a[i][j], i, j};
		}
	int l = 0, r = mx[0] - mn[0], ans = r;
	
	vector<int> dx = {-1,1,0,0}, dy = {0,0,-1,1};
	auto ok = [&](int i, int j) -> bool {
		return (i >= 0 && i < n && j >= 0 && j < m);
	};
	
	auto ch = [&]( int mid ) -> bool {
		//cout << mid << endl;
		vector<vector<int>> us1(n, vector<int> (m, 0));
		vector<vector<int>> us2(n, vector<int> (m, 0));
		
		queue<array<int,2>> q;
		q.push({mn[1], mn[2]});
		us1[mn[1]][mn[2]] = 1;
		while(q.size()){
			auto [i, j] = q.front();
			q.pop();
			//cout << i << ' ' << j << '\n';
			for(int k = 0; k < 4; k ++ ){
				int ni = i + dx[k], nj = j + dy[k];
				if(ok(ni, nj) && !us1[ni][nj] && a[ni][nj] - mn[0] <= mid){
					us1[ni][nj] = 1;
					q.push({ni, nj});
				}
			}
		};
		//cout << '\n';
		q.push({mx[1], mx[2]});
		us2[mx[1]][mx[2]] = 1;
		while(q.size()){
			auto [i, j] = q.front();
			q.pop();
			//cout << i << ' ' << j << '\n';
			for(int k = 0; k < 4; k ++ ){
				int ni = i + dx[k], nj = j + dy[k];
				if(ok(ni, nj) && !us2[ni][nj] && mx[0] - a[ni][nj] <= mid){
					us2[ni][nj] = 1;
					q.push({ni, nj});
				}
			}
		};
		//cout << '\n';
		for(int i = 0; i < n; i ++ )
			for(int j = 0; j < m; j ++ )
				if(!(us1[i][j] || us2[i][j]))return 0;
		
		return 1;
	};
	
	
	while( l <= r ) {
		int m = (l + r) >> 1;
		if(ch(m)){
			ans = m;
			r = m - 1;
		}else l = m + 1;
	};
	
	cout << ans << '\n';
};

signed main(){
	ios_base::sync_with_stdio();
	cin.tie(nullptr); cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	
	while(tt -- ){
		solve();
	};
	
};

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40