Submission #586902

#	Time	Username	Problem	Language	Result	Execution time	Memory
586902		dutinmeow	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1361 ms	54984 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int N, M;
	cin >> N >> M;
	vector<vector<int>> A(N, vector<int>(M));
	int vmn = INT_MAX, vmx = INT_MIN;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> A[i][j];
			vmn = min(vmn, A[i][j]);
			vmx = max(vmx, A[i][j]);
		}
	}

	int ans = INT_MAX;
	for (int i = 0; i < 4; i++) {
		int bl = 0, br = vmx - vmn;
		while (bl < br) {
			int bm = (bl + br) / 2;

			int bnd = 0, wrk = 1;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++)
					if (A[i][j] < vmx - bm)
						bnd = max(bnd, j + 1);
				for (int j = 0; j < M; j++) {
					if (vmn + bm < A[i][j]) {
						if (j < bnd) {
							wrk = 0;
							break;
						}
					}
				}
			}

			if (wrk)
				br = bm;
			else 
				bl = bm + 1;
		}

		ans = min(ans, bl);
		
		if (i == 0 || i == 2) {
			for (int i = 0; i < N / 2; i++)
				for (int j = 0; j < M; j++)
					swap(A[i][j], A[N - 1 - i][j]);
		} 
		if (i == 1) {
			for (int i = 0; i < N; i++)
				for (int j = 0; j < M / 2; j++)
					swap(A[i][j], A[i][M - 1 - j]);
		}
	}

	cout << ans << '\n';
}

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