Submission #361342

#	Time	Username	Problem	Language	Result	Execution time	Memory
361342		ogibogi2004	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	1218 ms	26196 KiB

burrow

#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 (stderr)

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;
      |                  ^~~~

• Subtask 1: 100 / 100