제출 #363984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
363984		NachoLibre	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	638 ms	37524 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
#undef wambule
#define wambule
#define sz(a) ((int)a.size())
typedef vector<int> vint;
#ifndef wambule
#include ".h"
#else
#endif

const int N = 2003, M = N;
int n, m, a[N][M], ox, on = 1e9, z;

void X() {
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m / 2; ++j) {
			swap(a[i][j], a[i][m - 1 - j]);
		}
	}
}

void Y() {
	for(int i = 0; i < n / 2; ++i) {
		for(int j = 0; j < m; ++j) {
			swap(a[i][j], a[n - 1 - i][j]);
		}
	}
}

bool C(int x) {
	int y = m;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < y; ++j) {
			if(ox - x > a[i][j]) {
				y = j;
				break;
			}
		}
		for(int j = y; j < m; ++j) {
			if(on + x < a[i][j]) {
				return 0;
			}
		}
	}
	return 1;
}

int D() {
	int l = 0, r = ox - on;
	while(l < r) {
		int m = (l + r) / 2;
		// cout << m << " " << C(m) << endl;
		if(m == 7) ++z;
		if(C(m)) {
			r = m;
		} else {
			l = m + 1;
		}
	}
	return l;
}

#ifdef wambule
mt19937 rnd(time(0));
int R(int l, int r) {
	return 1ll * rnd() % (r - l + 1) + l;
}

const int inf = 1e9 + 1;
int ffp;
void G(int i, int y, int lx = 0, int ln = inf, int rx = 0, int rn = inf) {
	if(i == n) {
		if(ln == inf || rn == inf) return;
		ffp = min(ffp, max(lx - ln, rx - rn));
		return;
	}
	for(int j = -1; j < y; ++j) {
		int nln = inf, nlx = 0, nrn = inf, nrx = 0;
		for(int jj = 0; jj <= j; ++jj) {
			nln = min(nln, a[i][jj]);
			nlx = max(nlx, a[i][jj]);
		}
		for(int jj = j + 1; jj < m; ++jj) {
			nrn = min(nrn, a[i][jj]);
			nrx = max(nrx, a[i][jj]);
		}
		G(i + 1, j + 1, max(nlx, lx), min(nln, ln), max(nrx, rx), min(nrn, rn));
	}
}

int V() {
	ffp = inf;
	G(0, m);
	Y();
	G(0, m);
	X();
	G(0, m);
	Y();
	G(0, m);
	X();
	return ffp;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int rtg = 1;
	if(rtg == 1) {
		cin >> n >> m;
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < m; ++j) {
				cin >> a[i][j];
				ox = max(ox, a[i][j]);
				on = min(on, a[i][j]);
			}
		}
		int fp = D();
		Y();
		fp = min(fp, D());
		X();
		fp = min(fp, D());
		Y();
		fp = min(fp, D());
		cout << fp << endl;
	} else if(rtg == 2) {
		n = m = 4;
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < m; ++j) {
				a[i][j] = R(0, 9);
				ox = max(ox, a[i][j]);
				on = min(on, a[i][j]);
			}
		}
		int fp = D();
		Y();
		fp = min(fp, D());
		X();
		fp = min(fp, D());
		Y();
		fp = min(fp, D());
		X();
		V();
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < m; ++j) {
				cout << a[i][j] << " ";
			}
			cout << endl;
		}
		cout << fp << " " << ffp << endl;
	}
	return 0;
}
#endif

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