Submission #4760

#	Time	Username	Problem	Language	Result	Execution time	Memory
4760		cki86201	Luxury burrow (IZhO13_burrow)	C++98	100 / 100	916 ms	9176 KiB

burrow

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

int n,m,k,ans2;
int inp[1010][1010];
int tmp[1010][1010];

typedef pair<int,int> Pi;
#define X first
#define Y second

vector <Pi> v;

bool check(int x)
{
	int i,j;
	for(i=0;i<n;i++){
		tmp[i][0]=(inp[i][0]>=x);
		for(j=1;j<m;j++)
			if(inp[i][j]>=x)tmp[i][j]=tmp[i][j-1]+1;
			else tmp[i][j]=0;
	}
	int mx = 0;
	for(j=0;j<m;j++){
		v.clear();
		for(i=0;i<=n;i++){
			int a = i;
			while(!v.empty() && v.back().Y >= tmp[i][j]){
				a=v.back().X;
				mx = max(mx,v.back().Y * (i - a));
				v.pop_back();
			}
			v.push_back(Pi(a,tmp[i][j]));
		}
	}
	if(mx>=k){ans2=mx;return true;}
	return false;
}

int main(){
	scanf("%d%d%d",&n,&m,&k);
	int i,j;
	for(i=0;i<n;i++){
		for(j=0;j<m;j++)scanf("%d",inp[i]+j);
	}
	int st=1,en=1e9,mi,ans;
	while(st<=en){
		mi = (st+en)>>1;
		if(check(mi))st=mi+1,ans=mi;
		else en=mi-1;
	}
	printf("%d %d",ans,ans2);
	return 0;
}

• Subtask 1: 100 / 100