oj.uz

답안 #535405

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535405 2022-03-10T08:37:08 Z amunduzbaev The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 227 ms 31812 KB 
#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;
			}
		}
		
		//~ if(d <= 18){
			//~ 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";
		//~ }
		
		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] = 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=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] = 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=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

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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 225 ms 31812 KB Output is correct
2 Incorrect 227 ms 31808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 225 ms 31812 KB Output is correct
2 Incorrect 227 ms 31808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 225 ms 31812 KB Output is correct
2 Incorrect 227 ms 31808 KB Output isn't correct
3 Halted 0 ms 0 KB -