oj.uz

Submission #262954

# Submission time Handle Problem Language Result Execution time Memory
262954 2020-08-13T11:26:31 Z sahil_k The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 1 ms 512 KB 
#include <iostream>
using namespace std;
#define MAXN 2005
int n, m;
int grid[MAXN][MAXN];
int min_v = 1e9, max_v = -1;
bool check (int x) {
	int pos = m;
	int cur = max_v;
	for (int i=0; i<n; i++) {
		for (int j=0; j<pos; j++) {
			if (grid[i][j]-min_v > x) {
				pos = j+1;
				break;
			}
		}
		for (int j=pos; j<m; j++) {
			cur = min(cur, grid[i][j]);
		}
	}
	if (max_v-cur <= x) return true;
	pos = m;
	cur = max_v;
	for (int i=n-1; i>=0; i--) {
		for (int j=0; j<pos; j++) {
			if (grid[i][j]-min_v > x) {
				pos = j+1;
				break;
			}
		}
		for (int j=pos; j<m; j++) {
			cur = min(cur, grid[i][j]);
		}
	}
	if (max_v-cur <= x) return true;
	pos = -1;
	cur = max_v;
	for (int i=0; i<n; i++) {
		for (int j=m-1; j>pos; j--) {
			if (grid[i][j]-min_v > x) {
				pos = j-1;
				break;
			}
		}
		for (int j=pos; j>=0; j--) {
			cur = min(cur, grid[i][j]);
		}
	}
	if (max_v-cur <= x) return true;
	pos = -1;
	cur = max_v;
	for (int i=n-1; i>=0; i--) {
		for (int j=m-1; j>pos; j--) {
			if (grid[i][j]-min_v > x) {
				pos = j-1;
				break;
			}
		}
		for (int j=pos; j>=0; j--) {
			cur = min(cur, grid[i][j]);
		}
	}
	if (max_v-cur <= x) return true;
	return false;
	/*
	pos = m;
	cur = min_v;
	for (int i=0; i<n; i++) {
		for (int j=0; j<pos; j++) {
			if (max_v-grid[i][j] > x) {
				pos = j+1;
				break;
			}
		}
		for (int j=pos; j<m; j++) {
			cur = max(cur, grid[i][j]);
		}
	}
	if (cur-min_v <= x) return true;
	pos = m;
	cur = min_v;
	for (int i=n-1; i>=0; i--) {
		for (int j=0; j<pos; j++) {
			if (max_v-grid[i][j] > x) {
				pos = j+1;
				break;
			}
		}
		for (int j=pos; j<m; j++) {
			cur = max(cur, grid[i][j]);
		}
	}
	if (cur-min_v <= x) return true;
	return false;
	*/
}
int main () {
	cin >> n >> m;
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			cin >> grid[i][j];
			min_v = min(min_v, grid[i][j]);
			max_v = max(max_v, grid[i][j]);
		}
	}
	int l = 0, r = 1e9, m, o;
	while (l <= r) {
		m = (l+r)/2;
		if (check(m)) {
			r = m-1; o = m;
		} else {
			l = m+1;
		}
	}
	cout << o << endl;
}

Compilation message

joioi.cpp: In function 'int main()':
joioi.cpp:115:10: warning: 'o' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |  cout << o << endl;
      |          ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -