Submission #993470

#	Time	Username	Problem	Language	Result	Execution time	Memory
993470		horezushol	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	4038 ms	92824 KiB

joioi

#include<bits/stdc++.h>
#define F first
#define S second
#define SZ(x) ((ll)(x).size())
inline void outlast() {
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
}
const char nl = '\n';
using namespace std;
using ll = long long;
// head

const ll N = 2100;
vector<vector<ll>> a(N, vector<ll> (N, 0));
ll h, w;

vector<vector<ll>> CIRCLE(const vector<vector<ll>>& matrix) {
    vector<vector<ll>> rotated(N, vector<ll>(N));    
    for (ll i = 1; i <= h; i++) {
        for (ll j = 1; j <= w; j++) {
            rotated[j][h-i+1] = matrix[i][j];
        }
    }
    swap(h, w);
    return rotated;
}


void solve() {
	cin >> h >> w;
	for (ll i = 1; i <= h; i ++) {
		for (ll j = 1; j <= w; j ++) {
			cin >> a[i][j];
		}
	}
	ll L = 0, R = 1e9;
	while (L + 1 < R) {
		ll mid = (L + R) / 2;
		bool ok = false;
		for (ll i = 0; i < 4; i ++) {
			a = CIRCLE(a);
			ll val = LLONG_MAX, posx = 0, posy = 0;
			for (ll i = 1; i <= h; i ++) {
				for (ll j = 1; j <= w; j ++) {
					if (a[i][j] < val) {
						val = a[i][j];
						posx = i;
						posy = j;
					}
				}
			}
			vector<ll> row(N, 0);
			for (ll i = 1; i <= h; i ++) {
				for (ll j = 1; j <= w; j ++) {
					if (a[i][j] <= val + mid) {
						row[i] ++;
					} else {
						break;
					}
				}
			}
			for (ll i = 2; i <= h; i ++) {
				row[i] = min(row[i], row[i-1]);
			}
			ll mn = LLONG_MAX, mx = LLONG_MIN;
			for (ll i = 1; i <= h; i ++) {
				for (ll j = row[i]+1; j <= w; j ++) {
					mn = min(mn, a[i][j]);
					mx = max(mx, a[i][j]);
				}
			}
			if (row[posx] >= posy && (mx == LLONG_MIN || mx - mn <= mid)) {
				ok = true;
			}
		}
		if (ok) {
			R = mid;
		} else {
			L = mid;
		}
	}
	cout << R;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	// outlast();
	ll tst = 1;
	// cin >> tst;
	while (tst --) {
		solve();
		cout << nl;
	}
}

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