Submission #1012751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012751		NintsiChkhaidze	The Kingdom of JOIOI (JOI17_joioi)	C++17	60 / 100	4030 ms	254972 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[3][N];
bool vis[N][N],cur[3][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);
}

bool get(bool k,int d){
	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[k][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]);
				}
			}

			if (mx2-mn2 > d) return 0;
			if (mx1-mn1 > d) return 0;
		}
	}

	return 1;
}

bool go1(int d){
	int mn0 = 2e9,mn1 = 2e9,l0,r0,l1,r1;
	for (int i = 1; i <= n; i++){
		mn0 = min(mn0,cnt[0][i]);
		mn1 = min(mn1,cnt[1][i]);
		l0 = m - mn0 + 1; r0 = m;
		l1 = 1; r1 = mn1;
		
		for (int j = 1; j <= m; j++){
			cur[1][i][j] = (j >= l1 && j <= r1);
			cur[0][i][j] = (j >= l0 && j <= r0);
		}
	}
	
	return (get(0,d)) || (get(1,d));
}

bool go2(int d){
	int mn0 = 2e9,mn1 = 2e9,l0,r0,l1,r1;
	for (int i = n; i >= 1; i--){
		mn0 = min(mn0,cnt[0][i]);
		mn1 = min(mn1,cnt[1][i]);
		l0 = m - mn0 + 1; r0 = m;
		l1 = 1; r1 = mn1;

		for (int j = 1; j <= m; j++){
			cur[1][i][j] = (j >= l1 && j <= r1);
			cur[0][i][j] = (j >= l0 && j <= r0);
		}
	}
	
	return (get(0,d)) || (get(1,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){
		int mid=(l+r)/2;
		go(X,Y,mid);

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

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

			for (int j = 1; j <= m; j++)
				vis[i][j] = 0;
		}

		if (go1(mid) || go2(mid)){
			ans = mid;
			r = mid-1;
		}else{
			l = mid + 1;
		}
	}
	
	cout<<ans<<endl;
}

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