Submission #1116894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116894		witek_cpp	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	1 ms	2384 KiB

joioi

#include <iostream>

using namespace std;

const int MAXN = 2001;

int n, m;

int tablica[MAXN][MAXN];
int p1[MAXN][MAXN];

int wynik = 1000000000;

int min_ele = 1000000000;

void obroc() {
	for (int i = 0; n > i; i++) {
		for (int j = 0; m > j; j++) {
			p1[m - 1 - j][i] = tablica[i][j];
		}
	}
	for (int i = 0; n > i; i++) {
		for (int j = 0; m > j; j++) {
			tablica[m - 1 -j][i] = p1[m - 1 - j][i];
		}
	}
	swap(m, n);
}

bool BS(int val) {
	int aktl_koniec = 1000000000;
	int p1;
	int max_r = -1000000000, min_r = 1000000000;
	for (int i = 0; n > i; i++) {
		p1 = -1;
		while (((p1 + 1) < m) && (tablica[i][p1 + 1] - min_ele) <= val && (aktl_koniec >= p1 + 1)) {
			p1++;
		}
		aktl_koniec = p1;
		for (int j = (p1 + 1); m > j; j++) {
			max_r = max(max_r, tablica[i][j]);
			min_r = min(min_r, tablica[i][j]);
		}
	}
	if ((max_r - min_r) <= val) {
		return true;
	} 
	return false;
}

int zrob_BS() {
	
	int l = 0, r = 1000000, mid;
	
	while (r > l) {
		mid = (l + r)/2;
		if (BS(mid)) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	return r;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	
	for (int i = 0; n > i; i++) {
		for (int j = 0; m > j; j++) {
			cin >> tablica[i][j];
			min_ele = min(min_ele, tablica[i][j]);
		}
	}
	wynik = zrob_BS();
	for (int i = 0; 3 > i; i++) {
		obroc();
		wynik = min(wynik, zrob_BS());
	}
	cout << wynik;
	return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40