Submission #1183288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183288		Paz15	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	597 ms	16156 KiB

joioi

//fast
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

#define rep(n) for(int i = 0 ; i<n ; i++)
#define all(x) x.begin(),x.end()
#define pb push_back

const int base = 2e3+7;
int a[base][base];
int n,m;
int mini,maks;

void flipx(){
	rep(n){
		for (int j = 0 ; j<m/2 ; j++){
			swap(a[i][j],a[i][m-j-1]);
		}
	}
}

void flipy(){
	for (int j = 0 ; j<m ; j++){
		rep(n/2){
			swap(a[i][j],a[n-i-1][j]);
		}
	}
}

bool dasie(int x){
	int last = m;
	int xd = 0;
	rep(n){
		int c = 0;
		for (int j = 0 ; j<m ; j++){
			if (a[i][j]<maks-x){
				c = j;
				break;
			}else c = j+1;
		}
		for (int j = min(c,last) ; j<m ; j++){
			xd = max(xd,a[i][j]);
		}
		last = min(c,last);
	}
	if (xd-mini<=x) return 1;
	return 0;
}

int wyn(){
	int p = -1;
	int k = 1e9;
	while (k-p>1){
		int s = (k+p)/2;
		if (dasie(s)) k = s;
		else p = s;
	}
	return k;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	cin >> n >> m;
	mini = 1e9+7;
	rep(n){
		for (int j = 0 ; j<m ; j++){
			cin >> a[i][j];
			mini = min(mini,a[i][j]);
			maks = max(maks,a[i][j]);
		}
	}
	int w = 1e9+7;
	w = min(w,wyn());
	flipx();
	w = min(w,wyn());
	flipy();
	w = min(w,wyn());
	flipx();
	w = min(w,wyn());
	cout << w << '\n';
	return 0;
}

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