Submission #5411

#	Time	Username	Problem	Language	Result	Execution time	Memory
5411		gs12006	Luxury burrow (IZhO13_burrow)	C++98	0 / 100	2000 ms	15276 KiB

burrow

#include <stdio.h>
#include <memory.h>

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

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]=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;
	scanf("%d %d %d",&n,&m,&k);
	for (i=0;i<n;i++) for (j=0;j<m;j++)
	{
		scanf("%d",&a[i][j]);
		if (a[i][j]<minn) minn=a[i][j];
		if (a[i][j]>maxn) maxn=a[i][j];
	}
	while (1)
	{
		if (maxn<=minn+1)
		{
			tt=f(maxn);
			if (tt>=k) printf("%d %d",maxn,tt);
			else printf("%d %d",minn,f(minn));
			break;
		}
		midn=(maxn+minn)/2;
		tt=f(midn);
		if (tt>k) minn=midn;
		else maxn=midn;
	}
}

• Subtask 1: 0 / 100