Submission #5402

#	Time	Username	Problem	Language	Result	Execution time	Memory
5402		Qwaz	Luxury burrow (IZhO13_burrow)	C++98	100 / 100	656 ms	13280 KiB

burrow

#include <cstdio>
#include <algorithm>

using namespace std;
const int MAX = 1020;

int h, w, minArea, data[MAX][MAX], valList[MAX*MAX], vFull;

void input(){
	scanf("%d%d%d", &h, &w, &minArea);

	int i, j;
	for(i = 1; i<=h; i++){
		for(j = 1; j<=w; j++){
			scanf("%d", &data[i][j]);
			valList[vFull++] = data[i][j];
		}
	}

	sort(valList, valList+vFull);
	vFull = unique(valList, valList+vFull)-valList;
}

int sum[MAX][MAX];

int calcArea(int pivot){
	int i, j;
	for(i = 1; i<=h; i++){
		for(j = 1; j<=w; j++){
			if(data[i][j] >= pivot) sum[i][j] = sum[i-1][j]+1;
			else sum[i][j] = 0;
		}
	}

	int ret = 0;
	for(i = 1; i<=h; i++){
		int stack[MAX], left[MAX], right[MAX], top;

		top = 0;
		for(j = 1; j<=w; j++){
			left[j] = 1;

			while(top && sum[i][stack[top-1]] >= sum[i][j])
				left[j] += left[stack[--top]];
			stack[top++] = j;
		}

		top = 0;
		for(j = w; j>=1; j--){
			right[j] = 1;

			while(top && sum[i][stack[top-1]] >= sum[i][j])
				right[j] += right[stack[--top]];
			stack[top++] = j;

			ret = max(ret, sum[i][j]*(left[j]+right[j]-1));
		}
	}

	return ret;
}

void solve(){
	int l = 0, r = vFull-1, last, m;
	while(l <= r){
		m = (l+r)>>1;

		if(calcArea(valList[m]) >= minArea){
			l = m+1;
			last = valList[m];
		}  else r = m-1;
	}

	printf("%d %d\n", last, calcArea(last));
}

int main(){
	input();

	solve();

	return 0;
}

• Subtask 1: 100 / 100