oj.uz

Submission #375583

# Submission time Handle Problem Language Result Execution time Memory
375583 2021-03-09T14:49:01 Z astoria The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 1 ms 364 KB 
#include "bits/stdc++.h"
using namespace std;

#define int long long
const int H=2005,W=2005;
int h,w,lo,hi;
int g[H][W];

bool check(int x){
	for(int i=1; i<=h; i++){
		int lopo=0;
		for(int j=1; j<=w; j++){
			if(lo+x < g[i][j]) break;
			lopo++;
		}
		int hipo=w+1;
		for(int j=w; j>=1; j--){
			if(hi-x > g[i][j]) break;
			hipo--;
		}
		if(lopo+1 < hipo) return 0;
	}
	return 1;
}


bool checkc(int x){
	for(int i=1; i<=h; i++){
		int lopo=0;
		for(int j=1; j<=w; j++){
			if(lo+x < g[i][j]) break;
			lopo++;
		}
		cout<<lopo<<' ';
		int hipo=w+1;
		for(int j=w; j>=1; j--){
			if(hi-x > g[i][j]) break;
			hipo--;
		}
		cout<<hipo<<endl;
		if(lopo+1 < hipo) return 0;
	}
	return 1;
}

void flip_row(){
	for(int i=1; i<=h; i++){
		for(int j=1; j<=w/2; j++){
			swap(g[i][j],g[i][w-j+1]);
		}
	}
}

void flip_col(){
	for(int j=1; j<=w; j++){
		for(int i=1; i<=h/2; i++){
			swap(g[i][j],g[h-i+1][j]);
		}
	}
}

bool f(int x){
	bool an=0;
	if(check(x)) an=1;
	flip_row();
	if(check(x)) an=1;
	flip_col();
	if(check(x)) an=1;
	flip_row();
	if(check(x)) an=1;
	flip_col();
	return an;
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin>>h>>w;
	lo=1e9+500; hi=-1e6;
	for(int j=0; j<=w+1; j++) g[0][j]=0;
	for(int i=1; i<=h; i++){
		g[i][0]=0;
		for(int j=1; j<=w; j++){
			cin>>g[i][j];
			lo=min(lo,g[i][j]);
			hi=max(hi,g[i][j]);
		}
		g[i][w+1]=0;
	}
	for(int j=0; j<=w+1; j++) g[h+1][j]=0;
	
	int l=0, r=1e9+100;
	while(l<r){
		int m=l+((r-l)/2);
		if(f(m)) r=m;
		else l=m+1;
	}
	cout<<l;
	
	//checkc(5);
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -