Submission #335302

#	Time	Username	Problem	Language	Result	Execution time	Memory
335302		ChrisT	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1134 ms	55020 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
const int MN = 2e3 + 3;
int a[MN][MN],n,m,x,y;
bool __check (int mid) { //a <= mid + min
	int big = mid + a[x][y];
	int mn = 1e9, mx = -1e9;
	auto upd = [&] (int v) {mn = min(mn,v); mx = max(mx,v);};
	vector<int> ed(n+1);
	for (int i = 1; i <= n; i++) {
		while (ed[i] < m && a[i][ed[i]+1] <= big) ++ed[i];
	}
	for (int i = n-1; i >= 1; i--) {
		ed[i] = min(ed[i],ed[i+1]);
	}
	if (ed[x] < y) return false;
	for (int i = 1; i <= n; i++) {
		for (int j = ed[i] + 1; j <= m; j++) {
			upd(a[i][j]);
		}
	}
	return mx - mn <= mid;
}
bool _check (int mid) {
	if (__check(mid)) return true;
	reverse(a+1,a+1+n);
	x = n+1-x;
	bool ok = __check(mid);
	x = n+1-x;
	reverse(a+1,a+1+n);
	return ok;
}
bool check (int mid) {
	if (_check(mid)) return true;
	for (int i = 1; i <= n; i++) reverse(a[i]+1,a[i]+1+m);
	y = m+1-y;
	bool ok = _check(mid);
	y = m+1-y;
	for (int i = 1; i <= n; i++) reverse(a[i]+1,a[i]+1+m);
	return ok;
}
int main() {
	scanf ("%d %d",&n,&m); x=y=1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf ("%d",&a[i][j]);
			if (a[i][j] < a[x][y]) {x = i; y = j;}
		}
	}
	int low = 0, high = 2e9, mid, ans = -1;
	while (low <= high) {
		mid = (low + high) / 2;
		if (check(mid)) high = (ans = mid) - 1;
		else low = mid + 1; 
	}
	printf ("%d\n",ans);
	return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |  scanf ("%d %d",&n,&m); x=y=1;
      |  ~~~~~~^~~~~~~~~~~~~~~
joioi.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |    scanf ("%d",&a[i][j]);
      |    ~~~~~~^~~~~~~~~~~~~~~

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