Submission #322553

#	Time	Username	Problem	Language	Result	Execution time	Memory
322553		Seanliu	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	852 ms	112620 KiB

joioi

#include <iostream>
#define ericxiao ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

const int maxN = 2e3 + 326, INF = 2e9 + 326;
int N, M, arr[maxN][maxN], narr[maxN][maxN], mx[maxN][maxN], mn[maxN][maxN], MX = -INF, MN = INF, ans = INF;

inline void rot(){
	for(int i = 0; i < N; i++) for(int j = 0; j < M; j++){
		narr[j][N - 1 - i] = arr[i][j];
	}
	swap(N, M);
	for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) arr[i][j] = narr[i][j];
}

int main(){
	ericxiao;
	cin >> N >> M;
	for(int i = 0; i < N; i++) for(int j = 0; j < M; j++){
		cin >> arr[i][j];
		MX = max(MX, arr[i][j]);
		MN = min(MN, arr[i][j]);
	}
	for(int jizz = 0; jizz < 4; jizz++){
		int _ans = 0;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				mx[i][j] = arr[i][j];
				if(i){
					mx[i][j] = max(mx[i][j], mx[i - 1][j]);
				}
				if(j){
					mx[i][j] = max(mx[i][j], mx[i][j - 1]);
				}
			}
		}
		for(int i = N - 1; i >= 0; i--){
			for(int j = M - 1; j >= 0; j--){
				mn[i][j] = arr[i][j];
				if(i < N - 2){
					mn[i][j] = min(mn[i][j], mn[i + 1][j]);
				}
				if(j < M - 2){
					mn[i][j] = min(mn[i][j], mn[i][j + 1]);
				}
			}
		}
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				_ans = max(_ans, min(MX - mn[i][j], mx[i][j] - MN));
			}
		}
		ans = min(ans, _ans);
		rot();
	}
	cout << ans << endl;
}

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