oj.uz

답안 #870380

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
870380 2023-11-07T14:17:37 Z phoenix0423 The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 0 ms 348 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int N = 998244353;
const int INF = 1e9;
const int maxn = 2005;
int a[maxn][maxn];

int main(void){
	fastio;
	int h, w;
	cin>>h>>w;
	int mn = INF, mx = 0;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			cin>>a[i][j];
			mn = min(mn, a[i][j]);
			mx = max(mx, a[i][j]);
		}
	}
	int ng = 0, ok = INF;
	while(ng + 1 < ok){
		int m = (ng + ok) / 2;
		int bad = 0;
		// vector<int> dp(5, 1); // [0] -> none, [1] -> down, [2] -> up, [3] -> full, [4] -> finished
		for(int j = 0; j < w; j++){
			int mngiv = INF, mxgiv = 0, mnget = INF, mxget = 0;
			for(int i = 0; i < h; i++){
				if(a[i][j] > mn + m) mnget = min(mnget, i), mxget = max(mxget, i);
				else if(a[i][j] < mx - m) mngiv = min(mngiv, i), mxgiv = max(mxgiv, i);
			}
			for(int i = 0; i < h; i++){
				if(a[i][j] > mn + m){
					if(i > mngiv && i < mxgiv) bad = 1;
				}
				else if(a[i][j] < mx - m){
					if(i > mnget && i < mxget) bad = 1;
				}
			}
			if(bad) break;
		}
		int type = 0;
		for(int j = 0; j < w; j++){
			int give = 0, get = 0;
			for(int i = 0; i < h; i++){
				if(a[i][j] > mn + m) {
					get = 1;
					if(give) break;
				}
				else if(a[i][j] < mx - m){
					give = 1;
					if(get){
						type = 1;
						break;
					}
				}
			}
			if(give && get) break;
		}
		// check validity
		int give = 0, get = 0, ndall = 0, ndz = 0;
		for(int j = 0; j < w; j++){
			if(a[0][j] > mn + m && a[h - 1][j] > mn + m && give) ndall = 1;
			else if(a[0][j] < mx - m && a[h][j] < mx - m && get) ndz = 1;
			int c1 = 0, c2 = 0;
			for(int i = 0; i < h; i++){
				if(a[i][j] > mn + m){
					c2 = 1, get = 1;
					if(ndz) bad = 1;
					if(c1 && type == 1) bad = 1;
				}
				else if(a[i][j] < mx - m){
					c1 = 1, give = 1;
					if(ndall) bad = 1;
					if(c2 && type == 0) bad = 1;
				}
			}
		}
		if(bad) ng = m;
		else ok = m;
	}
	cout<<ok<<"\n";
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 40.0

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