Submission #922949

#	Time	Username	Problem	Language	Result	Execution time	Memory
922949		OAleksa	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1406 ms	71068 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	int n, m;
  	cin >> n >> m;
  	vector<vector<int>> a(n, vector<int>(m));
  	int mn = 1e9, mx = 0;
  	for (int i = 0;i < n;i++) {
  		for (int j = 0;j < m;j++) {
  			cin >> a[i][j];
  			mn = min(mn, a[i][j]);
  			mx = max(mx, a[i][j]);
  		}
  	}
  	int l = 0, r = 1e9, ans = -1;
  	auto check = [&](int mid) {
  		int lst = -1, ok = 1;
  		for (int i = 0;i < n;i++) {
  			for (int j = 0;j < m;j++) {
  				if (a[i][j] > mn + mid)
  					lst = max(lst, j);
  			}
  			for (int j = 0;j < m;j++) {
  				if (j <= lst && a[i][j] < mx - mid)
  					ok = 0;
  			}
  		}
  		if (ok)
  			return ok;
  		reverse(a.begin(), a.end());
  		lst = -1;
  		ok = 1;
  		for (int i = 0;i < n;i++) {
  			for (int j = 0;j < m;j++) {
  				if (a[i][j] > mn + mid)
  					lst = max(lst, j);
  			}
  			for (int j = 0;j < m;j++) {
  				if (j <= lst && a[i][j] < mx - mid)
  					ok = 0;
  			}
  		}
  		if (ok)
  			return ok;
  		for (int i = 0;i < n;i++)
  			reverse(a[i].begin(), a[i].end());
  		lst = -1;
  		ok = 1;
  		for (int i = 0;i < n;i++) {
  			for (int j = 0;j < m;j++) {
  				if (a[i][j] > mn + mid)
  					lst = max(lst, j);
  			}
  			for (int j = 0;j < m;j++) {
  				if (j <= lst && a[i][j] < mx - mid)
  					ok = 0;
  			}
  		}
  		if (ok)
  			return ok;
  		reverse(a.begin(), a.end());
  		lst = -1;
  		ok = 1;
  		for (int i = 0;i < n;i++) {
  			for (int j = 0;j < m;j++) {
  				if (a[i][j] > mn + mid)
  					lst = max(lst, j);
  			}
  			for (int j = 0;j < m;j++) {
  				if (j <= lst && a[i][j] < mx - mid)
  					ok = 0;
  			}
  		}
  		return ok;
  	};
  	while (l <= r) {
  		int mid = (l + r) / 2;
  		if (check(mid)) {
  			ans = mid;
  			r = mid - 1;
  		}
  		else
  			l = mid + 1;
  	}
  	cout << ans << '\n';
  }
  return 0;
}

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