Submission #236425

#	Time	Username	Problem	Language	Result	Execution time	Memory
236425		GioChkhaidze	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1054 ms	70648 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
const int N=2004;
int n,m,Max,Min,ans;
int a[N][N],b[N][N];

bool check(int x) {
	int Col=0;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++)
			if (Max-x>a[i][j]) Col=max(Col,j);
		for (int j=1; j<=Col; j++)
			if (Min+x<a[i][j]) return false;
	}
	
	return true;
} 

void G() {
	int l=0,r=Max-Min,mid,res=-1;
	while (l<=r) {
		mid=(l+r)/2;
		if (check(mid))
			r=mid-1,res=mid;
				else
			l=mid+1;
	}
	if (res==-1) return ;
	ans=min(ans,res);
}

void Rotate() {
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++)
			b[i][j]=a[i][j];
		
	for (int i=1; i<=m; i++)
		for (int j=1; j<=n; j++) 
			a[i][j]=b[j][m-i+1];
		
	swap(n,m);
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	
	cin>>n>>m;
	Max=-1e9,Min=1e9;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++) {
			cin>>a[i][j];
			Max=max(Max,a[i][j]);
			Min=min(Min,a[i][j]);
		}
	
	ans=1e9;
	G();
	Rotate(); G();
	Rotate(); G();
	Rotate(); G();
	cout<<ans<<"\n";
}

Compilation message (stderr)

joioi.cpp:44:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

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