oj.uz

답안 #47529

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
47529 2018-05-05T02:47:47 Z aome 호화 벙커 (IZhO13_burrow) C++17
0 / 100
 2000 ms 680 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int n, m, K;
int res;
int l[N], r[N];
int a[N][N];
int b[N][N];
int f[N][N];

void solve(int x) {
	for (int i = 1; i <= m; ++i) {
		l[i] = i;
		while (l[i] > 1 && f[x][l[i] - 1] >= f[x][i]) l[i] = l[l[i] - 1];
	}
	for (int i = m; i >= 1; --i) {
		r[i] = i;
		while (r[i] < n && f[x][r[i] + 1] >= f[x][i]) r[i] = r[r[i] + 1];
	}
	for (int i = 1; i <= m; ++i) res = max(res, (r[i] - l[i] + 1) * f[x][i]);
}

void calc(int x) {
	for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) b[i][j] = a[i][j] >= x;
	for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) {
		if (b[i][j]) f[i][j] = f[i - 1][j] + 1; else f[i][j] = 0;
	}
	res = 0;
	for (int i = 1; i <= n; ++i) solve(i);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> K;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> a[i][j];
		}
	}
	int l = 1, r = 1e9;
	while (l < r) {
		int mid = (l + r + 1) >> 1; calc(mid);
		if (res >= K) l = mid; else r = mid - 1;
	}
	calc(l);
	cout << l << ' ' << res << '\n';
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 412 KB Output is correct
2 Correct 2 ms 560 KB Output is correct
3 Execution timed out 2023 ms 680 KB Time limit exceeded
4 Halted 0 ms 0 KB -