Submission #335287

#	Time	Username	Problem	Language	Result	Execution time	Memory
335287		ChrisT	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	2 ms	364 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);};
	for (int j = y-1; j > 0; j--) if (a[x][j] > big) return false;
	int lst = m;
	for (int i = x; i > 0; i--) {
		int ed = 0;
		while (ed < lst && a[i][ed+1] <= big) ++ed;
		for (int j = ed+1; j <= m; j++) upd(a[i][j]);
		lst = ed;
	}
	lst = m;
	for (int i = x+1; i <= n; i++) {
		int ed = 0;
		while (ed < lst && a[i][ed+1] <= big) ++ed;
		for (int j = ed+1; j <= m; j++) upd(a[i][j]);
		lst = ed;
	}
	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:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |  scanf ("%d %d",&n,&m); x=y=1;
      |  ~~~~~~^~~~~~~~~~~~~~~
joioi.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |    scanf ("%d",&a[i][j]);
      |    ~~~~~~^~~~~~~~~~~~~~~

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