Submission #535407

#	Time	Username	Problem	Language	Result	Execution time	Memory
535407		amunduzbaev	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2865 ms	102140 KiB

joioi

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long

const int N = 2005;
const int inf = 1e9;
int a[N][N], is[N][N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	int mn = 1e9;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
			mn = min(mn, a[i][j]);
		}
	}
	
	auto print = [&](int d){
		cout<<d<<"\n";
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++) cout<<is[i][j]<<" ";
			cout<<"\n";
		} cout<<"\n";
	};
	
	auto check = [&](int d){
		memset(is, 0, sizeof is);
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(a[i][j] <= mn + d) is[i][j] = 1;
			}
		}
		
		vector<int> pref(n), suff(n);
		for(int i=0;i<n;i++){
			int j=0;
			while(j<m && is[i][j]) j++;
			pref[i] = j;
			j=m-1;
			while(~j && is[i][j]) j--;
			suff[i] = j + 1;
		}
		
		{
			vector<int> tmp = pref;
			for(int i=1;i<n;i++) tmp[i] = min(tmp[i], tmp[i-1]);
			
			memset(is, 0, sizeof is);
			int M[2][2] = {
				{inf, 0},
				{inf, 0}
			};
			for(int i=0;i<n;i++){
				for(int j=0;j<tmp[i];j++) is[i][j] = 1;
				for(int j=0;j<m;j++){
					M[is[i][j]][0] = min(M[is[i][j]][0], a[i][j]);
					M[is[i][j]][1] = max(M[is[i][j]][1], a[i][j]);
				}
			}
			
			if(M[0][1] - M[0][0] <= d && M[1][1] - M[1][0] <= d){
				//~ print(d);
				return true;
			}
		}
		
		{
			vector<int> tmp = pref;
			for(int i=n-2;~i;i--) tmp[i] = min(tmp[i], tmp[i+1]);
			
			memset(is, 0, sizeof is);
			int M[2][2] = {
				{inf, 0},
				{inf, 0}
			};
			for(int i=0;i<n;i++){
				for(int j=0;j<tmp[i];j++) is[i][j] = 1;
				for(int j=0;j<m;j++){
					M[is[i][j]][0] = min(M[is[i][j]][0], a[i][j]);
					M[is[i][j]][1] = max(M[is[i][j]][1], a[i][j]);
				}
			}
			
			if(M[0][1] - M[0][0] <= d && M[1][1] - M[1][0] <= d){
				//~ print(d);
				return true;
			}
		}
		{
			vector<int> tmp = suff;
			for(int i=1;i<n;i++) tmp[i] = max(tmp[i], tmp[i-1]);
			
			memset(is, 0, sizeof is);
			int M[2][2] = {
				{inf, 0},
				{inf, 0}
			};
			for(int i=0;i<n;i++){
				for(int j=tmp[i];j<m;j++) is[i][j] = 1;
				for(int j=0;j<m;j++){
					M[is[i][j]][0] = min(M[is[i][j]][0], a[i][j]);
					M[is[i][j]][1] = max(M[is[i][j]][1], a[i][j]);
				}
			}
			
			if(M[0][1] - M[0][0] <= d && M[1][1] - M[1][0] <= d){
				//~ print(d);
				return true;
			}
		}
		
		{
			vector<int> tmp = suff;
			for(int i=n-2;~i;i--) tmp[i] = max(tmp[i], tmp[i+1]);
			
			memset(is, 0, sizeof is);
			int M[2][2] = {
				{inf, 0},
				{inf, 0}
			};
			for(int i=0;i<n;i++){
				for(int j=tmp[i];j<m;j++) is[i][j] = 1;
				for(int j=0;j<m;j++){
					M[is[i][j]][0] = min(M[is[i][j]][0], a[i][j]);
					M[is[i][j]][1] = max(M[is[i][j]][1], a[i][j]);
				}
			}
			
			if(M[0][1] - M[0][0] <= d && M[1][1] - M[1][0] <= d){
				//~ print(d);
				return true;
			}
		}
		
		return false;
	};
	
	int l = 0, r = inf;
	while(l < r){
		int m = (l + r) >> 1;
		if(check(m)) r = m;
		else l = m + 1;
	}
	
	cout<<l<<"\n";
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:23:7: warning: variable 'print' set but not used [-Wunused-but-set-variable]
   23 |  auto print = [&](int d){
      |       ^~~~~

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