Submission #1161326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161326		Nurislam	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	3396 ms	94492 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 rota = [&]() {
		vector<vector<int>> na(m, vector<int>(n));
		for(int nj = 0, j = m-1; j >= 0; nj ++, j -- ){
			for(int i = 0; i < n; i ++ )
				na[nj][i] = a[i][j];
		}
		
		a = na;
		swap(n, m);
	};
	
	auto ch = [&]( int mid ) -> bool {
		for(int k = 0; k < 4; k ++ ){
			int la = m-1, cmx = 0;
			for(int i = 0; i < n; i ++ ) {
				for(int j = 0; j < m; j ++ ){
					if(mx[0] - a[i][j] > mid) la = min(la, j-1);
					if(j > la){
						cmx = max(cmx, a[i][j]);
					}
				}
			}
			if(cmx - mn[0] <= mid) return 1;
			rota();
		}
		return 0;
	};
	
	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: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40