oj.uz

Submission #262958

# Submission time Handle Problem Language Result Execution time Memory
262958 2020-08-13T11:29:07 Z sahil_k The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 1 ms 384 KB 
#include <iostream>
using namespace std;
#define MAXN 2005
int n, m;
long long grid[MAXN][MAXN];
long long min_v = 1e12, max_v = -1;
bool check (long long x) {
	long long pos = m;
	long long 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;
}
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]);
		}
	}
	long long l = 0, r = 1e12, m, o;
	while (l <= r) {
		m = (l+r)/2;
		if (check(m)) {
			r = m-1; o = m;
		} else {
			l = m+1;
		}
	}
	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 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 0 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 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 0 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 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -