제출 #33288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
33288		huynd2001	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	4000 ms	39084 KiB

joioi

/*huypheu
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10
*/
//https://oj.uz/problem/view/JOI17_joioi

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

int mi[2007][3],ma[2007][3];
int a[2007][2007],ty[2007][2007],val[2007];
vector <int> v;
int n,m;
int mak,mik;

bool checko()
{
	for(int i=1;i<=n;i++) mi[i][1]=0,ma[i][1]=0,mi[i][2]=m+1,ma[i][2]=m+1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(ty[i][j]==1) mi[i][1]=j,ma[i][1]=j;
			if(ty[i][j]==3) ma[i][1]=j;
			if(ty[i][j]==2) break;
		}
		for(int j=m;j>=1;j--)
		{
			if(ty[i][j]==2) mi[i][2]=j,ma[i][2]=j;
			if(ty[i][j]==3) ma[i][2]=j;
			if(ty[i][j]==1) break;
		}
		if(ma[i][1]<ma[i][2]-1) return 0;
	}
	bool ok=0;
	for(int i=1;i<=n;i++)
	{
		if(i==1) val[i]=mi[i][1]; else
		{
			int k=max(val[i-1],mi[i][1]);
			if(k<=ma[i][1]) val[i]=k; else break;
		}
		if(i==n) ok=1;
	}
	if(ok) return 1;
	for(int i=1;i<=n;i++)
	{
		if(i==1) val[i]=ma[i][1]; else
		{
			int k=min(val[i-1],ma[i][1]);
			if(k>=mi[i][1]) val[i]=k; else break;
		}
		if(i==n) ok=1;
	}
	if(ok) return 1;
	return 0;
}

bool check(int len)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]<=mik+len) ty[i][j]=1;
			if(a[i][j]>=mak-len) ty[i][j]=2;
			if(a[i][j]<=mik+len && a[i][j]>=mak-len) ty[i][j]=3;
			if(a[i][j]>mik+len && a[i][j]<mak-len) return 0;
		}
	}
	if(checko()) return 1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]>=mik+len) ty[i][j]=1;
			if(a[i][j]<=mak-len) ty[i][j]=2;
			if(a[i][j]<=mik+len && a[i][j]>=mak-len) ty[i][j]=3;
			if(a[i][j]>mik+len && a[i][j]<mak-len) return 0;
		}
	}
	if(checko()) return 1;
	return 0;
}

int main()
{
	cin >> n >> m;
	set <int> se;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin >> a[i][j];
			se.insert(a[i][j]);
		}
	}
	// v.push_back(0);
	for(set<int>::iterator it=se.begin();it!=se.end();it++)
	{
		v.push_back(*it);
	}
	mik=v[0],mak=v[v.size()-1];
	int l=0,r=(mak-mik);
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid)) r=mid; else l=mid+1;
	}
	cout << l << endl;
	return 0;
}

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