#include<bits/stdc++.h>
using namespace std;
const int MAXN=1024;
int a[MAXN][MAXN];
int n,m,k;
int b[MAXN][MAXN];
int p[MAXN][MAXN];
int tl[MAXN],tr[MAXN];
stack<pair<int,int> >st;
int find_max_area()
{
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(b[i][j]==1)p[i][j]=p[i-1][j]+1;
else p[i][j]=0;
}
}
for(int i=1;i<=n;i++)
{
while(!st.empty())st.pop();
for(int j=1;j<=m;j++)
{
while(!st.empty()&&p[i][j]<=st.top().first)
{
st.pop();
}
if(st.empty())tl[j]=0;
else tl[j]=st.top().second;
st.push({p[i][j],j});
}
while(!st.empty())st.pop();
for(int j=m;j>=1;j--)
{
while(!st.empty()&&p[i][j]<=st.top().first)
{
st.pop();
}
if(st.empty())tr[j]=m+1;
else tr[j]=st.top().second;
st.push({p[i][j],j});
}
for(int j=1;j<=m;j++)
{
ans=max(ans,p[i][j]*(tr[j]-tl[j]-1));
}
}
return ans;
}
void fill(int t)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]>=t)b[i][j]=1;
else b[i][j]=0;
}
}
}
int main()
{
cin>>n>>m>>k;
vector<int>v;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
v.push_back(a[i][j]);
}
}
sort(v.begin(),v.end());
int l=0,r=v.size()-1,mid,ans=-1,ans1;
while(l<=r)
{
mid=(l+r)/2;
int t=v[mid];
fill(t);
int gg=find_max_area();
if(gg>=k)
{
ans=v[mid];
ans1=gg;
l=mid+1;
}
else r=mid-1;
}
cout<<ans<<" "<<ans1<<endl;
return 0;
}
Compilation message
burrow.cpp: In function 'int main()':
burrow.cpp:91:18: warning: 'ans1' may be used uninitialized in this function [-Wmaybe-uninitialized]
91 | cout<<ans<<" "<<ans1<<endl;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
620 KB |
Output is correct |
5 |
Correct |
1 ms |
748 KB |
Output is correct |
6 |
Correct |
2 ms |
876 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
9 ms |
1644 KB |
Output is correct |
9 |
Correct |
20 ms |
3180 KB |
Output is correct |
10 |
Correct |
49 ms |
3432 KB |
Output is correct |
11 |
Correct |
76 ms |
4328 KB |
Output is correct |
12 |
Correct |
47 ms |
6760 KB |
Output is correct |
13 |
Correct |
59 ms |
2452 KB |
Output is correct |
14 |
Correct |
156 ms |
6644 KB |
Output is correct |
15 |
Correct |
161 ms |
6496 KB |
Output is correct |
16 |
Correct |
171 ms |
7020 KB |
Output is correct |
17 |
Correct |
214 ms |
8032 KB |
Output is correct |
18 |
Correct |
436 ms |
11868 KB |
Output is correct |
19 |
Correct |
541 ms |
12840 KB |
Output is correct |
20 |
Correct |
841 ms |
18260 KB |
Output is correct |
21 |
Correct |
906 ms |
20720 KB |
Output is correct |
22 |
Correct |
1218 ms |
26196 KB |
Output is correct |
23 |
Correct |
1215 ms |
26128 KB |
Output is correct |
24 |
Correct |
847 ms |
17824 KB |
Output is correct |
25 |
Correct |
1002 ms |
19284 KB |
Output is correct |