Submission #1081120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081120		Trent	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	3363 ms	134116 KiB

joioi

#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i=0; i<(x); ++i)
#define REP(i, a, b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(), x.end()
#define boost() cin.sync_with_stdio(0); cin.tie(0)
typedef long long ll;
typedef vector<int> vi;

const int MN = 2010;
int a[MN][MN];
int h, w;
struct cell{int r, c, val;};
cell bv[MN * MN];
int osa[MN][MN], xsa[MN][MN];

void setOnes(int lBound, int hBound) {
	REP(r, 1, h+1) REP(c, 1, w+1) osa[r][c] = xsa[r][c] = 0;
	forR(i, h*w) {
		if(bv[i].val <= lBound) osa[bv[i].r][bv[i].c] += 1;
		if(bv[i].val >= hBound) xsa[bv[i].r][bv[i].c] += 1;
	}
}
void propagate(int arr[MN][MN], int dr, int dc) {
	for(int i = (dr == 1 ? 1 : h); i > 0 && i <= h; i += dr) {
		for(int j = (dc == 1 ? 1 : w); j > 0 && j <= w; j += dc) {
			arr[i][j] += arr[i-dr][j] + arr[i][j-dc] - arr[i-dr][j-dc];
		}
	}
}
bool hasCommon() {
	REP(r, 1, h+1) REP(c, 1, w+1) if(osa[r][c] > 0 && xsa[r][c] > 0) return true;
	return false;
}
bool possible(int mDiff) {
	int lBound = bv[h*w-1].val - mDiff - 1;
	int hBound = bv[0].val + mDiff + 1;

	setOnes(lBound, hBound);
	propagate(osa, 1, 1);
	propagate(xsa, -1, -1);
	if(!hasCommon()) return true;

	setOnes(lBound, hBound);
	propagate(osa, 1, -1);
	propagate(xsa, -1, 1);
	if(!hasCommon()) return true;

	setOnes(lBound, hBound);
	propagate(osa, -1, 1);
	propagate(xsa, 1, -1);
	if(!hasCommon()) return true;

	setOnes(lBound, hBound);
	propagate(osa, -1, -1);
	propagate(xsa, 1, 1);
	if(!hasCommon()) return true;

	return false;
}
int calcAns() {
	int cells = h * w;
	sort(bv, bv + cells, [](cell a, cell b){return a.val < b.val;});

	possible(5);

	int lo = -1, hi = 1e9;
	while(hi - lo > 1) {
		int mid = (lo+hi)/2;
		if(possible(mid)) hi = mid;
		else lo = mid;
	}
	return hi;
}

signed main() {
	boost();
	cin >> h >> w;
	REP(r, 1, h+1) REP(c, 1, w+1) {
		cin >> a[r][c];
		bv[(r-1)*w + (c-1)] = {r, c, a[r][c]};
	}
	int bes = calcAns();
	cout << bes << '\n';
}

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