Submission #647575

#	Time	Username	Problem	Language	Result	Execution time	Memory
647575		ymm	The Kingdom of JOIOI (JOI17_joioi)	C++17	60 / 100	4078 ms	189692 KiB

joioi

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 2048;
int a[N][N];
int n, m;

int len[N];

bool can_extend(int i, int mx)
{
	if (i > 0 && len[i-1] <= len[i])
		return 0;
	if (len[i] == m || a[i][len[i]] > mx)
		return 0;
	return 1;
}

int solve()
{
	multiset<int> s1, s2;
	vector<pair<int,int>> alts;
	memset(len, 0, sizeof(len));
	Loop (i,0,n) Loop (j,0,m) {
		alts.push_back({a[i][j], i});
		s2.insert(a[i][j]);
	}
	sort(alts.begin(), alts.end());
	int ans = 2e9;
	for (auto [mx, row] : alts) {
		Loop (r,row,n) {
			if (!can_extend(r, mx))
				break;
			while (can_extend(r, mx)) {
				s1.insert(a[r][len[r]]);
				s2.erase(s2.find(a[r][len[r]]));
				len[r]++;
			}
		}
		if (s1.empty() || s2.empty())
			continue;
		ans = min(ans, max(*s1.rbegin() - *s1.begin(),
		                   *s2.rbegin() - *s2.begin()));
	}
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop (i,0,n) Loop (j,0,m)
		cin >> a[i][j];
	int ans = 2e9;
	ans = min(ans, solve());
	Loop (i,0,n/2) Loop (j,0,m)
		swap(a[i][j], a[n-1-i][j]);
	ans = min(ans, solve());
	Loop (i,0,n) Loop (j,0,m/2)
		swap(a[i][j], a[i][m-1-j]);
	ans = min(ans, solve());
	Loop (i,0,n/2) Loop (j,0,m)
		swap(a[i][j], a[n-1-i][j]);
	ans = min(ans, solve());
	cout << ans << '\n';
}

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