Submission #1012730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012730		NintsiChkhaidze	The Kingdom of JOIOI (JOI17_joioi)	C++17	60 / 100	4042 ms	225956 KiB

joioi

#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define ll long long
using namespace std;

const int N = 2e3 + 3;
int a[N][N],n,m,mn,mx,cnt[N];
bool vis[N][N],cur[N][N];

void clear(){
	for (int i=1;i<=n;i++)
		for(int j = 1; j <= m;j++)
			vis[i][j]=0;
}
void go(int x,int y,int d){
	if (x < 1 || y < 1 || x > n || y > m || vis[x][y]) return;
	if (a[x][y] - mn > d) return;
	vis[x][y] = 1;
	go(x+1,y,d);
	go(x-1,y,d);
	go(x,y+1,d);
	go(x,y-1,d);
}

int get(){
	int mn1=-1,mx1=-1,mn2=-1,mx2=-1;
	for (int i= 1; i <= n; i++){
		for (int j= 1;j<=m;j++){
			if(cur[i][j]){
				if (mn1 == -1) {
					mn1 = mx1 = a[i][j];
				}else{
					mn1 = min(mn1,a[i][j]);
					mx1 = max(mx1,a[i][j]);
				}
			}else{	
				if (mn2 == -1) {
					mn2 = mx2 = a[i][j];
				}else{
					mn2 = min(mn2,a[i][j]);
					mx2 = max(mx2,a[i][j]);
				}
			}
		}
	}

	return max(mx2-mn2,mx1-mn1);
}

bool go1(int d,bool dir){
	int mnn = 2e9;
	for (int i = 1; i <= n; i++){
		mnn = min(mnn,cnt[i]);
		int l = 1,r = m;
		if (!dir) l = m - mnn + 1;
		else r = mnn;
		for (int j = 1; j <= m; j++)
			cur[i][j] = (j >= l && j <= r);
	}
	
	return (get() <= d);
}

bool go2(int d,bool dir){
	int mnn = 2e9;
	for (int i = n; i >= 1; i--){
		mnn = min(mnn,cnt[i]);
		int l = 1,r = m;
		if (!dir) l = m - mnn + 1;
		else r = mnn;
		for (int j = 1; j <= m; j++)
			cur[i][j] = (j >= l && j <= r);
	}
	
	return (get() <= d);
}

signed main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	cin>>n>>m;

	mn = 2e9;
	int X = 0,Y=0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cin >> a[i][j];
			if (a[i][j] < mn){
				X=i,Y=j;
				mn=a[i][j];
			}
			mx=max(mx,a[i][j]);
		}
	}

	int l = 0,r = mx - mn,ans=mx-mn;
	while (l <= r){
		clear();
		int mid=(l+r)/2;
		go(X,Y,mid);

		for (int i = 1; i <= n; i++){
			cnt[i] = m;
			for (int j = m; j >= 1; j--){
				if (!vis[i][j]){
					cnt[i] = m - j;
					break;
				}
			}
		}

		if (go1(mid,0) || go2(mid,0)){
			ans=mid;
			r=mid-1;
			continue;
		}

		for (int i = 1; i <= n; i++){
			cnt[i] = m;
			for (int j = 1; j <= m; j++){
				if (!vis[i][j]){
					cnt[i] = j - 1;
					break;
				}
			}
		}

		if (go1(mid,1) || go2(mid,1)){
			ans=mid;
			r=mid-1;
			continue;
		}

		l = mid + 1;
	}
	
	cout<<ans<<endl;
}

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