oj.uz

Submission #172583

# Submission time Handle Problem Language Result Execution time Memory
172583 2020-01-02T06:13:47 Z songc The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 2 ms 376 KB 
#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]);
	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

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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -