제출 #89850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89850		Dat160601	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	3 ms	960 KiB

joioi

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

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

bool Check(int x, int n, int m){
	int cur = m, mi = 2e9, mx = 0;
	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) 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(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
			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;
	}
	cout << mid;
}

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