Submission #172584

#	Time	Username	Problem	Language	Result	Execution time	Memory
172584		songc	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1101 ms	26248 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M, ans;
int gm=1234567890, mx, my;
int A[2020][2020];
int P[2020];

bool chk(int k){
	for (int i=1; i<=N; i++) for (P[i]=0; A[i][P[i]+1]-gm<=k && P[i]<M; P[i]++);
	int Max=0, Min=1234567890, t=M;
	for (int i=1; i<=N; i++){
		t = min(t, P[i]);
		if (i==mx && t<my){
			Max = 1234567890;
			Min = 0;
			break;
		}
		for (int j=t+1; j<=M; j++){
			Max = max(Max, A[i][j]);
			Min = min(Min, A[i][j]);
		}
	}
	if (Max-Min <= k) return true;

	Max=0, Min=1234567890, t=M;
	for (int i=N; i>=1; i--){
		t = min(t, P[i]);
		if (i==mx && t<my){
			Max = 1234567890;
			Min = 0;
			break;
		}
		for (int j=t+1; j<=M; j++){
			Max = max(Max, A[i][j]);
			Min = min(Min, A[i][j]);
		}
	}
	if (Max-Min <= k) return true;
	return false;
}

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]);
		if (gm > A[i][j]) gm = A[i][j], mx = i, my = j;
	}
	int L=0, H=1'000'000'000;
	while (L<=H){
		int mid = (L+H)/2;
		if (chk(mid)) ans = mid, H = mid-1;
		else L = mid+1;
	}
	L=0, H=ans;
	for (int i=1; i<=N; i++) for (int j=1; j<=M/2; j++) swap(A[i][j], A[i][M-j+1]);
	my = M-my+1;
	while (L<=H){
		int mid = (L+H)/2;
		if (chk(mid)) ans = mid, H = mid-1;
		else L = mid+1;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
joioi.cpp:48:8: 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