Submission #47529

#	Time	Username	Problem	Language	Result	Execution time	Memory
47529		aome	Luxury burrow (IZhO13_burrow)	C++17	0 / 100	2023 ms	680 KiB

burrow

#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