Submission #20964

#	Time	Username	Problem	Language	Result	Execution time	Memory
20964		kdh9949	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	3649 ms	33584 KiB

joioi

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

int n, m, mn = 1e9, a[2010][2010], b[2010][2010];

void rot(){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			b[j][n + 1 - i] = a[i][j];
		}
	}
	swap(n, m);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			a[i][j] = b[i][j];
		}
	}
}

int can(int k){
	for(int dum = 0; dum < 4; dum++){
		int lst = m, omx = 0, omn = 1e9;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= lst; j++){
				if(a[i][j] > mn + k){ lst = j - 1; break; }
			}
			for(int j = lst + 1; j <= m; j++){
				omx = max(omx, a[i][j]);
				omn = min(omn, a[i][j]);
			}
		}
		if(omx - omn <= k) return 1;
		if(dum < 3) rot();
	}
	return 0;
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			scanf("%d", a[i] + j);
			mn = min(mn, a[i][j]);
		}
	}
	int s = 0, e = 1e9;
	while(s <= e){
		int mid = (s + e) / 2;
		if(can(mid)) e = mid - 1;
		else s = mid + 1;
	}
	printf("%d\n", s);
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:39:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
joioi.cpp:42:25: 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