Submission #1288222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288222		Jawad_Akbar_JJ	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	2151 ms	16128 KiB

joioi

#include <iostream>

using namespace std;
int a[2005][2005], Max;

bool poss(int n, int m, int k){
	int mx = -1, mn = 1e9, id = 0;

	for (int j=m;j>=1;j--){
		int ind = n;
		while (ind > id and Max - a[ind][j] <= k)
			ind--;
		id = ind;
		while (ind > 0)
			mx = max(mx, a[ind][j]), mn = min(mn, a[ind][j]), ind--;
	}
	return (mx == -1 or mx - mn <= k);
}

int getMin(int n, int m){
	int l = -1, r = 1e9 + 7;

	while (l + 1 < r){
		int mid = (l + r) / 2;
		if (poss(n, m, mid))
			r = mid;
		else
			l = mid;
	}
	return r;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m, Mn;
	cin>>n>>m;

	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++)
			cin>>a[i][j], Max = max(Max, a[i][j]);
	}
	Mn = getMin(n, m);

	for (int i=1;i<=n;i++){
		for (int j=1;j+j<=m;j++)
			swap(a[i][j], a[i][m - j + 1]);
	}
	Mn = min(Mn, getMin(n, m));

	for (int i=1;i + i <= n;i++){
		for (int j=1;j<=m;j++)
			swap(a[i][j], a[n - i + 1][j]);
	}
	Mn = min(Mn, getMin(n, m));

	for (int i=1;i<=n;i++){
		for (int j=1;j+j<=m;j++)
			swap(a[i][j], a[i][m - j + 1]);
	}
	Mn = min(Mn, getMin(n, m));

	cout<<Mn<<'\n';
}

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