Submission #254573

#	Time	Username	Problem	Language	Result	Execution time	Memory
254573		babo	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	4072 ms	102504 KiB

joioi

#include <bits/stdc++.h>
#define L long long

using namespace std;

L n,m;
L totma=0,totmi=1000000000ll;
L a[2020][2020];
L c[2020][2020];
L rowma[2020],rowmi[2020];
L colma[2020],colmi[2020];

void clear(){
	L i;
	for(i=1;i<=n;i++)
		rowma[i]=0,rowmi[i]=1000000000ll;
	for(i=1;i<=m;i++)
		colma[i]=0,colmi[i]=1000000000ll;
}

void clear2(){
	L i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			c[i][j]=0;
}

bool ok2(L dis){
	L mamin=1000000000ll,mimax=0;
	L i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			if(c[i][j]) mamin=min(mamin,a[i][j]);
			else mimax=max(mimax,a[i][j]);
		}
	return totma-mamin<=dis&&mimax-totmi<=dis;
}

bool ok(L dis){
	L i,j;
	clear();
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(a[i][j]>totmi+dis)
			{
				rowma[i]=max(rowma[i],j);
				rowmi[i]=min(rowmi[i],j);
				colma[j]=max(colma[j],i);
				colmi[j]=min(colmi[j],i);
			}
	L now;
	clear2();
	now=n+1;
	for(j=m;j>=1;j--)
	{
		now=min(now,colmi[j]);
		for(i=now;i<=n;i++) c[i][j]=1;
	}
	if(ok2(dis)) return 1;
	clear2();
	now=n+1;
	for(j=1;j<=m;j++)
	{
		now=min(now,colmi[j]);
		for(i=now;i<=n;i++) c[i][j]=1;
	}
	if(ok2(dis)) return 1;
	clear2();
	now=0;
	for(j=1;j<=m;j++)
	{
		now=max(now,colma[j]);
		for(i=1;i<=now;i++) c[i][j]=1;
	}
	if(ok2(dis)) return 1;
	clear2();
	now=0;
	for(j=m;j>=1;j--)
	{
		now=max(now,colma[j]);
		for(i=1;i<=now;i++) c[i][j]=1;
	}
	if(ok2(dis)) return 1;

	return 0;
}

int main()
{
	scanf("%lld %lld",&n,&m);
	L i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			scanf("%lld",&a[i][j]);
			totma=max(totma,a[i][j]);
			totmi=min(totmi,a[i][j]);
		}
	}
	L s=0,e=1000000000ll;
	while(s<e)
	{
		L mid=(s+e)/2;
		if(ok(mid)) e=mid;
		else s=mid+1;
	}
	printf("%lld",s);
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~
joioi.cpp:97:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld",&a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~

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