Submission #47531

#	Time	Username	Problem	Language	Result	Execution time	Memory
47531		aome	Luxury burrow (IZhO13_burrow)	C++17	0 / 100	2067 ms	616 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() {
	scanf("%d %d %d", &n, &m, &K);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			scanf("%d", &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';
}

Compilation message (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
burrow.cpp:39:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100