Submission #519115

#	Time	Username	Problem	Language	Result	Execution time	Memory
519115		AdamGS	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1092 ms	70504 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e3+7, INF=1e9+7;
int A[LIM][LIM], T[LIM][LIM], n, m;
bool f(int x) {
	int ma=0, mi=INF;
	rep(i, n) rep(j, m) {
		ma=max(ma, A[i][j]);
		mi=min(mi, A[i][j]);
	}
	rep(i, n) rep(j, m) {
		T[i][j]=0;
		if(A[i][j]-mi<=x) ++T[i][j];
		if(ma-A[i][j]<=x) T[i][j]+=2;
		if(!T[i][j]) return false;
	}
	bool ok=true;
	int lst=m;
	rep(i, n) {
		int akt=0;
		while(akt<lst && T[i][akt]!=1) ++akt;
		lst=akt;
		for(int j=m-1; j>=akt; --j) if(T[i][j]==2) ok=false;
	}
	if(ok) return true;
	ok=true;
	lst=m;
	rep(i, n) {
		int akt=0;
		while(akt<lst && T[i][akt]!=2) ++akt;
		lst=akt;
		for(int j=m-1; j>=akt; --j) if(T[i][j]==1) ok=false;
	}
	if(ok) return true;
	ok=true;
	lst=-1;
	rep(i, n) {
		int akt=m-1;
		while(akt>lst && T[i][akt]!=1) --akt;
		lst=akt;
		for(int j=akt; j>=0; --j) if(T[i][j]==2) ok=false;
	}
	if(ok) return true;
	ok=true;
	lst=-1;
	rep(i, n) {
		int akt=m-1;
		while(akt>lst && T[i][akt]!=2) --akt;
		lst=akt;
		for(int j=akt; j>=0; --j) if(T[i][j]==1) ok=false;
	}
	return ok;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	rep(i, n) rep(j, m) cin >> A[i][j];
	int p=0, k=INF;
	while(p<k) {
		int sr=(p+k)/2;
		if(f(sr)) k=sr; else p=sr+1;
	}
	cout << p << '\n';
}

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