oj.uz

답안 #47811

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
47811 2018-05-07T14:16:12 Z jun6873 호화 벙커 (IZhO13_burrow) C++11
0 / 100
 3 ms 760 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];
bool b[1004][1004];

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

	int ans = 0;
	memset(c, 0, sizeof(c));
	for (int i=1; i<=h; i++) {
		for (int j=1; j<=w; j++) {
			if (b[i][j]) 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+1<r) {
		int m = (l+r)/2;
		if (f(m) >= k) l = m;
		else r = m;
	}

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

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 540 KB Output is correct
2 Correct 2 ms 708 KB Output is correct
3 Correct 2 ms 708 KB Output is correct
4 Correct 2 ms 708 KB Output is correct
5 Incorrect 3 ms 760 KB Output isn't correct
6 Halted 0 ms 0 KB -