#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
using namespace std;
const int N = 2e5 + 5;
main(){
int n, m, k;
cin >> n >> m >> k;
vector < vector <int> > v (n + 1, vector <int> (m + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> v[i][j];
}
}
int ans = 0;
auto check = [&](int x){
vector < vector <int> > p(n + 1, vector <int> (m + 1, 0));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
p[i][j] = (v[i][j] >= x) + p[i - 1][j];
}
}
for(int i = 1; i <= n; i++){
deque <int> q;
ans = 0;
for(int j = 1 ; j <= m; j++){
int ind = j;
while(!q.empty() && p[i][j] <= p[i][q.front()]){
ans = max(ans, p[i][q.front()] * (j - q.front()));
p[i][q.front()] = p[i][j];
ind = min(ind, q.front());
q.pop_front();
}
q.push_front(ind);
}
while(!q.empty()){
ans = max(((m + 1) - q.front()) * p[i][q.front()], ans);
q.pop_front();
}
}
//cout << x <<" " << ans << endl;
return (ans >= k);
};
int l = 1, r = 1e9;
while(r - l > 1){
int mid = (l + r) >> 1;
if(check(mid)){
l = mid;
}else
r = mid;
}
check(l);
cout << l <<" " << ans;
}
Compilation message
burrow.cpp:13:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
13 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
