oj.uz

Submission #5402

# Submission time Handle Problem Language Result Execution time Memory
5402 2014-04-30T11:12:12 Z Qwaz Luxury burrow (IZhO13_burrow) C++
100 / 100
 656 ms 13280 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13280 KB Output is correct
2 Correct 0 ms 13280 KB Output is correct
3 Correct 0 ms 13280 KB Output is correct
4 Correct 0 ms 13280 KB Output is correct
5 Correct 0 ms 13280 KB Output is correct
6 Correct 0 ms 13280 KB Output is correct
7 Correct 0 ms 13280 KB Output is correct
8 Correct 4 ms 13280 KB Output is correct
9 Correct 4 ms 13280 KB Output is correct
10 Correct 20 ms 13280 KB Output is correct
11 Correct 44 ms 13280 KB Output is correct
12 Correct 16 ms 13280 KB Output is correct
13 Correct 28 ms 13280 KB Output is correct
14 Correct 60 ms 13280 KB Output is correct
15 Correct 72 ms 13280 KB Output is correct
16 Correct 92 ms 13280 KB Output is correct
17 Correct 56 ms 13280 KB Output is correct
18 Correct 236 ms 13280 KB Output is correct
19 Correct 232 ms 13280 KB Output is correct
20 Correct 520 ms 13280 KB Output is correct
21 Correct 496 ms 13280 KB Output is correct
22 Correct 656 ms 13280 KB Output is correct
23 Correct 644 ms 13280 KB Output is correct
24 Correct 376 ms 13280 KB Output is correct
25 Correct 292 ms 13280 KB Output is correct