Submission #375591

#	Time	Username	Problem	Language	Result	Execution time	Memory
375591		astoria	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	3400 ms	16236 KiB

joioi

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

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

bool check(int x){
	int losen=w+1;
	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++;
		}
		losen=min(losen,lopo);
		int hipo=w+1;
		for(int j=w; j>=1; j--){
			if(hi-x > g[i][j]) break;
			hipo--;
		}
		if(losen + 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: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40