제출 #4760

#제출 시각아이디문제언어결과실행 시간메모리
4760cki86201Luxury burrow (IZhO13_burrow)C++98
100 / 100
916 ms9176 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...