Submission #33289

#	Time	Username	Problem	Language	Result	Execution time	Memory
33289		huynd2001	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2266 ms	33700 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()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin >> a[i][j];
		}
	}
	mik=a[1][1],mak=a[1][1];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			mik=min(mik,a[i][j]);
			mak=max(mak,a[i][j]);
		}
	}
	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: 40 / 40