Submission #33287

#	Time	Username	Problem	Language	Result	Execution time	Memory
33287		huynd2001	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	0 ms	33544 KiB

joioi

/*huypheu
8 6
23 23 10 11 16 21
15 26 19 28 19 20
25 26 28 16 15 11
11 8 19 11 15 24
14 19 15 14 24 11
10 8 11 7 6 14
23 5 19 23 17 17
18 11 21 14 20 16
*/
//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(v[mid]-v[1])) r=mid; else l=mid+1;
	}
	cout << v[l]-v[1] << endl;
	return 0;
}

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