oj.uz

답안 #299106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
299106 2020-09-14T13:40:46 Z reymontada61 The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 1 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m;
const int MXN = 2005;
int arr[MXN][MXN];
int mn = INT_MAX, mx = INT_MIN, ans;

int pfmax[MXN][MXN];
int sfmin[MXN][MXN];

bool works(int k) {
	
	int last_used = INT_MAX;
	
	for (int i=1; i<=n; i++) {
		int pos = 0;
		while (pos + 1 <= m && pfmax[i][pos] <= mn + k) {
			pos++;
		}
		pos = min(pos, last_used);
		last_used = pos;
		if (sfmin[i][pos+1] < mx - k) {
			return false;
		}
	}
	
	return true;
	
}

void prep() {
	
	for (int i=1; i<=n; i++) {
		pfmax[i][0] = INT_MIN;
		pfmax[i][1] = arr[i][1];
		for (int j=2; j<=m; j++) {
			pfmax[i][j] = max(pfmax[i][j-1], arr[i][j]);
		}
		sfmin[i][m+1] = INT_MAX;
		sfmin[i][m] = arr[i][m];
		for (int j=m-1; j>=1; j--) {
			sfmin[i][j] = min(sfmin[i][j+1], arr[i][j]);
		}
	}
	
}

int copytemp[MXN][MXN];

void rot() {
	
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			copytemp[j][n-i+1] = arr[i][j];
		}
	}
	
	swap(n, m);
	
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			arr[i][j] = copytemp[i][j];
		}
	}
	
}

signed main() {

	cin >> n >> m;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			cin >> arr[i][j];
			mn = min(mn, arr[i][j]);
			mx = max(mx, arr[i][j]);
		}
	}
	
	ans = mx - mn;
	
	for (int X=0; X<4; X++) {

		prep();
	
		int low = 0;
		int high = INT_MAX / 2;
		
		while (low + 1 < high) {
			int mid = (low + high) / 2;
			if (works(mid)) {
				high = mid;
			}
			else {
				low = mid;
			}
		}
		
		if (works(low)) ans = min(ans, low);
		else ans = min(ans, high);
		
		rot();
		
	}
	
	cout << ans << endl;

}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 40.0

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