Submission #51555

#	Time	Username	Problem	Language	Result	Execution time	Memory
51555		Vinhspm	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	3497 ms	136496 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define FOR(a, b, c) for(int a = b; a <= c; ++a)
const int N = 2009;
const int oo = 1e9 + 10;
const int mod = 1e9 + 7;
int n, m, ans = oo, imin = oo;
int a[N][N], tmp[N][N], Rmin[N][N], Rmax[N][N], pos[N];
void _rorate()	{
	for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j)
		tmp[j][n - i + 1] = a[i][j];
	swap(n, m);
	for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j)
		a[i][j] = tmp[i][j];
}
bool check(int val)	{ 
	// we save 
	for(int i = 1; i <= n; ++i)	{
		pos[i] = m + 1;
		for(int j = 1; j <= m; ++j) if(a[i][j] - imin > val) {
			pos[i] = j; break;
		}
	}
	for (int i = 1; i <= n; ++i)	{
		Rmin[i][m + 1] = oo, Rmax[i][m + 1] = 0;
		for (int j = m; j >= 1; --j) {
			Rmin[i][j] = min(Rmin[i][j + 1], a[i][j]);
			Rmax[i][j] = max(Rmax[i][j + 1], a[i][j]);
		}
	}
	int cur = oo, curmin = oo, curmax = 0;
	for(int i = 1; i <= n; ++i) 	{
		cur = min(cur, pos[i] - 1);
		curmin = min(curmin, Rmin[i][cur + 1]);
		curmax = max(curmax, Rmax[i][cur + 1]);
	}
	return ( curmax - curmin <= val );
}
void solve()	{
	int l = 0, r = oo;
	while(r > l) 	{
		int mid = (l + r) /2;
		if(check(mid) == true) r = mid;
		else l = mid + 1;
	}
	if(check(l)) ans = min(ans, l);
}
signed main()
{
	//freopen("test.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	FOR(i, 1, n) FOR(j, 1, m) cin >> a[i][j], imin = min(imin, a[i][j]); 
	solve(); 
	_rorate(); solve();
	_rorate(); solve();
	_rorate(); solve();
	cout << ans;
}

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