Submission #89857

#	Time	Username	Problem	Language	Result	Execution time	Memory
89857		Dat160601	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1967 ms	93864 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

int n, m, mini = 2e9, maxi = 0, a[2007][2007], sv[2007][2007];

int read(){
	char p;
	while((p = getchar())){
		if(p < '0' || p > '9') continue;
		break;
	}
	int ret = p - '0';
	while((p = getchar())){
		if(p >= '0' && p <= '9'){
			ret *= 10;
			ret += p - '0';
		}
		else break;
	}
	return ret;
}

bool Check(int x, int n, int m){
	int cur = m, mi = 2e9, mx = 0;
	bool ok = true;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= cur; j++){
			if(sv[i][j] - mini > x){
				cur = j - 1;
				break;
			}
		}
		for(int j = cur + 1; j <= m; j++){
			mi = min(mi, sv[i][j]), mx = max(mx, sv[i][j]);
		}
		if(mx - mi > x){
			ok = false;
			break;
		}
	}
	if(ok) return true;
	cur = 1, mi = 2e9, mx = 0;
	for(int i = 1; i <= n; i++){
		for(int j = m; j >= cur; j--){
			if(sv[i][j] - mini > x){
				cur = j + 1;
				break;
			}
		}
		for(int j = cur - 1; j >= 1; j--){
			mi = min(mi, sv[i][j]), mx = max(mx, sv[i][j]);
		}
		if(mx - mi > x) return false;
	}
	return true;
}

bool check(int x){
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sv[i][j] = a[i][j];
	if(Check(x, n, m)) return true;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sv[i][j] = a[n - i + 1][j];
	if(Check(x, n, m)) return true;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sv[j][i] = a[i][j];
	if(Check(x, m, n)) return true;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sv[j][i] = a[i][m - j + 1];
	if(Check(x, m, n)) return true;
	return false;
}

int main(){
	n = read(), m = read();
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			a[i][j] = read();
			mini = min(mini, a[i][j]);
			maxi = max(maxi, a[i][j]);
		}
	}
	int l = 0, r = maxi, mid = (l + r) / 2;
	while(l < r){
		if(check(mid)) r = mid;
		else l = mid + 1;
		mid = (l + r) / 2;
	}
	printf("%d", mid);
}

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