#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
stack<int> st;
int a[N][N], cp[N<<1], sz = 0, dp[2][N], fr[N], bk[N], b[N];
signed main(){
int m, n, k; scanf("%d %d %d", &m, &n, &k);
for(int i = 0; i<m; ++i) for(int j = 0; j<n; ++j){ scanf("%d", &a[i][j]); cp[sz++] = a[i][j];}
if(!k){ puts("1000000000"); return 0;}
sort(cp, cp+sz); sz = unique(cp, cp+sz) - cp;
int low = 0, high = sz-1;
pair<int,int> ans = {0, 0};
while(low <= high){
int mid = low + ((high-low)>>1), t = cp[mid];
bool ch = false;
fill(dp[0], dp[0]+n, 0); fill(dp[1], dp[1]+n, 0);
for(int i = 0; i<m; ++i){
int I[2] = {i&1, !(i&1)};
for(int j = 0; j<n; ++j) b[j] = dp[I[0]][j] = dp[I[1]][j] + (a[i][j] >= t);
while(!st.empty()) st.pop();
for(int j = 0; j<n; ++j){
while(!st.empty() && b[st.top()] >= b[j]) st.pop();
fr[j] = (!st.empty()) ? st.top() : -1;
st.push(j);
}
while(!st.empty()) st.pop();
for(int j = n-1; j>=0; --j){
while(!st.empty() && b[st.top()] >= b[j]) st.pop();
bk[j] = (!st.empty()) ? st.top() : n;
st.push(j);
}
for(int j = 0; j<n; ++j){ ++fr[j]; --bk[j];}
for(int j = 0; j<n; ++j){
int tmp = b[j] * (bk[j] - fr[j] + 1);
if(tmp >= k){ ans = max(ans, make_pair(t, tmp)); ch = true;}
}
}
if(ch) low = mid+1;
else high = mid-1;
}
printf("%d %d", ans.first, ans.second);
}
Compilation message
burrow.cpp: In function 'int main()':
burrow.cpp:7:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
7 | int m, n, k; scanf("%d %d %d", &m, &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
burrow.cpp:8:58: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | 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 |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
