Submission #158114

#	Time	Username	Problem	Language	Result	Execution time	Memory
158114		ZwariowanyMarcin	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1235 ms	70504 KiB

joioi

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl;
#define ios cin.tie(0); ios_base::sync_with_stdio(0)	
	
		
using namespace std;

int n, m;
int a[2002][2002], p[2002][2002];
int ans = 1000000001;
int maks;
int row, col;

void obrot() {
	FOR(i, 1, n)
		FOR(j, 1, m)
			p[j][n - i + 1] = a[i][j];
	int rr = col;
	int cc = n - row + 1;
	swap(n, m);
	row = rr;
	col = cc;
	FOR(i, 1, n)
		FOR(j, 1, m) 
			a[i][j] = p[i][j];
}

int bad[2002];

bool ok(int w) {
	int mini = maks - w;
	FOR(i, 1, n + 1)
		bad[i] = 0;
	for(int i = n; 1 <= i; --i) {
		for(int j = m; 1 <= j; --j) {
			if(a[i][j] < mini) {
				bad[i] = j;
				break;
			}
		}
		bad[i] = max(bad[i], bad[i + 1]);
	}
	if(bad[row] >= col)
		return 0;
	int Max = -1;
	int Min = 1e9 + 111;
	FOR(i, 1, n)
		FOR(j, 1, m) {
			if(j <= bad[i]) {
				Max = max(Max, a[i][j]);
				Min = min(Min, a[i][j]);
			}
		}
	//cout << Max << " " << Min << " " << w << endl;
	return Max - Min <= w;
}

void solve() {
	int l = 0;
	int r = 1000000000;
	while(l < r) {
		int m = (l + r) / 2;
		if(ok(m))
			r = m;
		else
			l = m + 1;
	}
	ans = min(ans, l);
}
	
					
int main() {	
	scanf("%d %d", &n, &m);
	FOR(i, 1, n)
		FOR(j, 1, m) {
			scanf("%d", &a[i][j]);
			if(a[i][j] > maks) {
				maks = a[i][j];
				row = i;
				col = j;
			}
		}
	int k = 4;
	while(k--) {
		obrot();
		
		/*FOR(i, 1, n) {
			FOR(j, 1, m)
				cout << a[i][j] << " ";
			cout << endl;
		}
		
		printf("\n\n");
		*/
		solve();
	}
	printf("%d", ans);
	
				
	return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
joioi.cpp:87:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~

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