Submission #47818

#	Time	Username	Problem	Language	Result	Execution time	Memory
47818		jun6873	Luxury burrow (IZhO13_burrow)	C++11	0 / 100	3 ms	556 KiB

burrow

#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);
		}
		while (!st.empty()) st.pop();
		for (int j=w; ~j; j--) {
			while (!st.empty() and st.top().x > c[j]) {
				ans = max(ans, st.top().x * (st.top().y - j));
				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<r) {
		int m = (l+r+1)/2;
		if (f(m) >= k) l = m;
		else r = m-1;
	}

	cout << l << ' ' << f(l) << '\n';
}

• Subtask 1: 0 / 100