Submission #993472

#	Time	Username	Problem	Language	Result	Execution time	Memory
993472		horezushol	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	3297 ms	91268 KiB

joioi

#include<bits/stdc++.h>
#define F first
#define S second
#define SZ(x) ((int)(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 int N = 2100;
vector<vector<int>> a(N, vector<int> (N, 0));
vector<vector<int>> rotated(N, vector<int>(N));    
int h, w;

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


void solve() {
	cin >> h >> w;
	for (int i = 1; i <= h; i ++) {
		for (int j = 1; j <= w; j ++) {
			cin >> a[i][j];
		}
	}
	int L = 0, R = 1e9;
	vector<int> row(N, 0);
	while (L + 1 < R) {
		int mid = (L + R) / 2;
		bool ok = false;
		for (int i = 0; i < 4; i ++) {
			a = CIRCLE(a);
			int val = INT_MAX, posx = 0, posy = 0;
			for (int i = 1; i <= h; i ++) {
				for (int j = 1; j <= w; j ++) {
					if (a[i][j] < val) {
						val = a[i][j];
						posx = i;
						posy = j;
					}
				}
			}
			for (int i = 1; i <= h; i ++) {
				row[i] = 0;
				for (int j = 1; j <= w; j ++) {
					if (a[i][j] <= val + mid) {
						row[i] ++;
					} else {
						break;
					}
				}
			}
			for (int i = 2; i <= h; i ++) {
				row[i] = min(row[i], row[i-1]);
			}
			int mn = INT_MAX, mx = INT_MIN;
			for (int i = 1; i <= h; i ++) {
				for (int j = row[i]+1; j <= w; j ++) {
					mn = min(mn, a[i][j]);
					mx = max(mx, a[i][j]);
				}
			}
			if (row[posx] >= posy && (mx == INT_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();
	int tst = 1;
	// cin >> tst;
	while (tst --) {
		solve();
		cout << nl;
	}
}

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