Submission #5413

#	Time	Username	Problem	Language	Result	Execution time	Memory
5413		gs12006	Luxury burrow (IZhO13_burrow)	C++98	92 / 100	2000 ms	19572 KiB

burrow

#include <stdio.h>
#include <algorithm>
using namespace std;

int a[1100][1100];
int s[1100][2];
int d[1100][1100];
int ans[1100][1100];
int n,m;
int nl[1100000];

int f(int x)
{
	int i,j,t,max=0;
	for (i=0;i<n;i++) for (j=0;j<m;j++) ans[i][j]=d[i][j]=0;
	for (i=0;i<m;i++) if (a[0][i]>=x) d[0][i]=1;
	for (i=0;i<m;i++) for (j=1;j<n;j++) if(a[j][i]>=x) d[j][i]=d[j-1][i]+1;
	for (i=0;i<n;i++)
	{
		for (j=0;j<m;j++) if (d[i][j]>0)
		{
			t=0;
			for (;d[i][j]!=0&&j<m;j++,t++)
			{
				for (;t>0&&s[t-1][0]>d[i][j];t--) ans[i][s[t-1][1]]+=j-s[t-1][1];
				s[t][0]=d[i][j];
				s[t][1]=j;
			}
			for (;t>0;t--) ans[i][s[t-1][1]]+=j-s[t-1][1];
		}
		for (j=m-1;j>=0;j--) if (d[i][j]>0)
		{
			t=0;
			for (;d[i][j]!=0&&j>=0;j--,t++)
			{
				for (;t>0&&s[t-1][0]>d[i][j];t--) ans[i][s[t-1][1]]+=s[t-1][1]-j;
				s[t][0]=d[i][j];
				s[t][1]=j;
			}
			for (;t>0;t--) ans[i][s[t-1][1]]+=s[t-1][1]-j;
		}
		for (j=0;j<m;j++) if (ans[i][j]>0) ans[i][j]--;
		for (j=0;j<m;j++) if (ans[i][j]>0) ans[i][j]*=d[i][j];
	}
	for (i=0;i<n;i++) for (j=0;j<m;j++) if (ans[i][j]>max) max=ans[i][j];
	return max;
}

int main()
{
	int i,j,k,minn=1<<30,maxn=0,midn,tt,rl;
	scanf("%d %d %d",&n,&m,&k);
	rl=n*m;
	for (i=0;i<n;i++) for (j=0;j<m;j++)
	{
		scanf("%d",&a[i][j]);
		nl[m*i+j]=a[i][j];
	}
	sort(nl,nl+n*m);
	for (i=0;i<n*m-1;i++)
	{
		if (nl[i]==nl[i+1])
		{
			nl[i]=1<<30;
			rl--;
		}
	}
	sort(nl,nl+n*m);
	minn=0;
	maxn=rl-1;
	while (1)
	{
		if (maxn<=minn+1)
		{
			tt=f(nl[maxn]);
			if (tt>=k) printf("%d %d",nl[maxn],tt);
			else printf("%d %d",nl[minn],f(nl[minn]));
			break;
		}
		midn=(maxn+minn)/2;
		tt=f(nl[midn]);
		if (tt>=k) minn=midn;
		else maxn=midn;
	}
}

• Subtask 1: 92 / 100