Submission #254596

#	Time	Username	Problem	Language	Result	Execution time	Memory
254596		babo	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1188 ms	197368 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 nucolmax[2020][2020];
L xamlocun[2020][2020];
L nucolmin[2020][2020];
L nimlocun[2020][2020];
L colma[2020],colmi[2020];

void clear(){
	L i;
	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 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)
			{
				colma[j]=max(colma[j],i);
				colmi[j]=min(colmi[j],i);
			}
	L now;
	L mamin,mimax;

	mamin=1000000000ll,mimax=0;
	now=n+1;
	for(j=m;j>=1;j--)
	{
		now=min(now,colmi[j]);
		mamin=min(mamin,nimlocun[now][j]);
		mimax=max(mimax,nucolmax[now-1][j]);
	}
	if(totma-mamin<=dis&&mimax-totmi<=dis) return 1;
	mamin=1000000000ll,mimax=0;
	now=n+1;
	for(j=1;j<=m;j++)
	{
		now=min(now,colmi[j]);
		mamin=min(mamin,nimlocun[now][j]);
		mimax=max(mimax,nucolmax[now-1][j]);
	}
	if(totma-mamin<=dis&&mimax-totmi<=dis) return 1;
	mamin=1000000000ll,mimax=0;
	now=0;
	for(j=1;j<=m;j++)
	{
		now=max(now,colma[j]);
		mamin=min(mamin,nucolmin[now][j]);
		mimax=max(mimax,xamlocun[now+1][j]);
	}
	if(totma-mamin<=dis&&mimax-totmi<=dis) return 1;
	mamin=1000000000ll,mimax=0;
	now=0;
	for(j=m;j>=1;j--)
	{
		now=max(now,colma[j]);
		mamin=min(mamin,nucolmin[now][j]);
		mimax=max(mimax,xamlocun[now+1][j]);
	}
	if(totma-mamin<=dis&&mimax-totmi<=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]);
		}
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			nucolmax[i][j]=max(nucolmax[i-1][j],a[i][j]);
	for(i=n;i>=1;i--)
		for(j=1;j<=m;j++)
			xamlocun[i][j]=max(xamlocun[i+1][j],a[i][j]);
	
		for(j=1;j<=m;j++)
			nucolmin[0][j]=nimlocun[n+1][j]=1000000000ll;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			nucolmin[i][j]=min(nucolmin[i-1][j],a[i][j]);
	for(i=n;i>=1;i--)
		for(j=1;j<=m;j++)
			nimlocun[i][j]=min(nimlocun[i+1][j],a[i][j]);
	/*for(i=1;i<=n;i++,puts(""))
		for(j=1;j<=m;j++)
			printf("%lld ",nucolmax[i][j]);
	puts("nucolmax");

	for(i=1;i<=n;i++,puts(""))
		for(j=1;j<=m;j++)
			printf("%lld ",nucolmin[i][j]);
	puts("nucolmin");

	for(i=1;i<=n;i++,puts(""))
		for(j=1;j<=m;j++)
			printf("%lld ",xamlocun[i][j]);
	puts("xamlocun");

	for(i=1;i<=n;i++,puts(""))
		for(j=1;j<=m;j++)
			printf("%lld ",nimlocun[i][j]);
	puts("nimlocun");


	for(i=1;i<=n;i++,puts(""))
		for(j=1;j<=m;j++)
			printf("%lld ",nimlocun[i][j]);
	puts("nimlocun");*/
	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:98:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(i=n;i>=1;i--)
  ^~~
joioi.cpp:102:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(j=1;j<=m;j++)
   ^~~
joioi.cpp:84: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:90: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: 40 / 40