Submission #47812

# Submission time Handle Problem Language Result Execution time Memory
47812 2018-05-07T14:36:44 Z jun6873 Luxury burrow (IZhO13_burrow) C++11
0 / 100
2 ms 708 KB
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pint;
#define x first
#define y second

int h, w, k, a[1004][1004], c[1004];

int f(int k) {
	int ans = 0;
	memset(c, 0, sizeof(c));
	for (int i=1; i<=h; i++) {
		for (int j=1; j<=w; j++) {
			if (a[i][j] >= k) c[j]++;
			else c[j] = 0;
		}

		stack<pint> st;
		for (int j=1; j<=w+1; j++) {
			while (!st.empty() and st.top().x > c[j]) {
				ans = max(ans, st.top().x * (j - st.top().y));
				st.pop();
			}
			st.emplace(c[j], j);
		}
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> h >> w >> k;
	for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) cin >> a[i][j];

	int l = 0, r = 1e9 + 2;
	while (l+1<r) {
		int m = (l+r)/2;
		if (f(m) >= k) l = m;
		else r = m;
	}

	cout << l << ' ' << f(l) << '\n';
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 556 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Incorrect 2 ms 708 KB Output isn't correct
6 Halted 0 ms 0 KB -