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