#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';
}
| # |
Verdict |
Execution time |
Memory |
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 |
- |
