Submission #1019319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019319		Aika	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	1 ms	348 KiB

joioi

#include <bits/stdc++.h>
#define int long long
#define Aiko ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define pb push_back
using namespace std;
const int  INF=1e9; 
signed main(){
	int h, w, i, j;
	cin>>h>>w;
	vector<vector<int>>a(h,vector<int>(w));
	int  mx=0,mn=INF;
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			cin>>a[i][j];
			mn=min(mn,a[i][j]);
			mx=max(mx,a[i][j]);
		}
	}
	auto fun=[&](int t){
		vector<vector<int>>color(h,vector<int>(w));
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				if(abs(a[i][j]-mn)<=t)color[i][j]=1;
			}
		}
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				if(color[i][j]!=1&&abs(a[i][j]-mx)<=t)color[i][j]=2;
				else if(abs(a[i][j]-mx)<=t)color[i][j]=3;
			}
		}
		vector<int>ans(h),ans1(h),ans2(w),ans3(w);
		for(i=0;i<h;i++){
			bool a2=0;
			for(j=0;j<w;j++){
				if(color[i][j]==1)ans[i]=j;
				if(color[i][j]==2&&a2==0){
					a2=1;
					ans1[i]=j;
				}
			}
		}
		for(i=0;i<h;i++){
			bool a2=0;
			for(j=0;j<h;j++){
				if(color[i][j]==1)ans[i]=j;
				if(color[i][j]==2&&a2==0){
					a2=1;
					ans1[i]=j;
				}
			}
		}
		for(i=0;i<w;i++){
			bool a2=0;
			for(j=0;j<h;j++){
				if(color[i][j]==1)ans2[i]=j;
				if(color[i][j]==2&&a2==0){
					a2=1;
					ans3[i]=j;
				}
			}
		}
		bool a1=0;
		for(i=0;i<h;i++){
			if(ans[i]>ans1[i])a1=1;
		}
		for(i=0;i<w;i++){
			if(ans2[i]>ans3[i])a1=1;
		}
		if(a1==1)return false;
		else return true;
	};
	int l=0,r=1e9+7;
	while(r>l+1){
		int m=(l+r)>>1;
		if(fun(m))r=m;
		else l=m;
		//cout<<l<<' '<<r<<endl;
	}
	if(fun(r))cout<<r;
	else cout<<l;
	
}		

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40