제출 #370332

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

joioi

#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
#define endl '\n'

int n, m;
vector<vi> mat;
const int INF = 1e9;
int fin;
vi nums;

void solve() {
	int l = 0, r = (int) nums.size()-1, ans = r;
	vi wd(n);
	while (l < r) {
		int mid = (l+r)/2;
		bool valid = true;
		for_(i, 0, n) {
			int pt = -1;
			for_(j, 0, m) {
				if (mat[i][j] > nums[mid]) break;
				pt = j;
			}
			if (i > 0) pt = min(pt, wd[i-1]);
			wd[i] = pt;
		}
		
		int mn = INF;
		if (valid) for_(i, 0, n) for_(j, wd[i]+1, m) {
			mn = min(mn, mat[i][j]);
		}
		if (nums.back()-mn > nums[mid]-nums[0]) valid = false;
		if (!valid) l = mid+1;
		else {
			r = ans = mid;
		}
	}
	
	fin = min(fin, nums[ans]-nums[0]);
}

void rotate() {
	vector<vi> temp(m, vi(n));
	for (int j = m-1; j >= 0; j--) {
		for_(i, 0, n) temp[m-j-1][i] = mat[i][j];
	}
	swap(n, m);
	swap(mat, temp);
}

void rotateAndSolve() {
	for_(i, 0, 4) {
		solve();
		rotate();
	}
}


int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	mat.resize(n, vi(m)); nums.reserve(n*m);
	for_(i, 0, n) for_(j, 0, m) {
		cin >> mat[i][j];
		nums.push_back(mat[i][j]);
	}
	
	sort(nums.begin(), nums.end());
	fin = nums.back()-nums[0];
	rotateAndSolve();
	for_(i, 0, n) for_(j, 0, m) mat[i][j] = -mat[i][j];
	reverse(nums.begin(), nums.end());
	for_(i, 0, nums.size()) nums[i] = -nums[i];
	rotateAndSolve();
	
	cout << fin << endl;
	
	
	return 0;
}

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