#include <cstdio>
#include <algorithm>
const int N = 1005;
int m, n, k, a[N][N], cp[N<<1], up[N][N], fr[N], bk[N], st[N], sz;
signed main(){
scanf("%d %d %d", &m, &n, &k); sz = 0;
for(int i = 0; i<m; ++i) for(int j = 0; j<n; ++j) scanf("%d", &a[i][j]), cp[sz++] = a[i][j];
std::sort(cp, cp+sz); sz = std::unique(cp, cp+sz) - cp;
int low = 0, high = sz-1;
std::pair<int,int> ans;
while(low <= high){
int mid = low + ((high-low)>>1), t = cp[mid], mx = 0;
bool ch = false;
for(int i = 0; i<m; ++i){
for(int j = 0; j<n; ++j) up[i][j] = (i ? up[i-1][j] : 0) + (a[i][j] >= t);
sz = 0;
for(int j = 0; j<n; ++j){
while(sz > 0 && up[i][st[sz-1]] >= up[i][j]) --sz;
fr[j] = sz ? st[sz-1] : -1;
st[sz++] = j;
}
sz = 0;
for(int j = n-1; j>=0; --j){
while(sz > 0 && up[i][st[sz-1]] >= up[i][j]) --sz;
bk[j] = sz ? st[sz-1] : n;
st[sz++] = j;
}
for(int j = 0; j<n; ++j) ++fr[j], --bk[j];
for(int j = 0; j<n; ++j) if(up[i][j] * (bk[j] - fr[j] + 1) >= k){ mx = std::max(mx, up[i][j] * (bk[j] - fr[j] + 1)); ch = true;}
}
if(ch) low = mid+1, ans = std::make_pair(t, mx);
else high = mid-1;
}
printf("%d %d", ans.first, ans.second);
}
Compilation message
burrow.cpp: In function 'int main()':
burrow.cpp:6:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
6 | scanf("%d %d %d", &m, &n, &k); sz = 0;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
burrow.cpp:7:57: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
7 | for(int i = 0; i<m; ++i) for(int j = 0; j<n; ++j) scanf("%d", &a[i][j]), cp[sz++] = a[i][j];
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
