Submission #673579

#	Time	Username	Problem	Language	Result	Execution time	Memory
673579		Baytoro	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	1036 ms	25760 KiB

burrow

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define int long long
#define endl '\n'
void fopn(string name){
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
const int INF=1e18,mod=998244353;
int n,m,k;
int h[1005][1005],a[1005][1005];
int area=0;
int get_area(vector<int> vec){
	int N=vec.size();
	vec.resize(N+2);
	vector<int> l(N+2),r(N+2);
	vec[0]=vec[N+1]=-INF;
	stack<int> st;
	st.push(0);
	for(int i=1;i<=N;i++){
		while(vec[st.top()]>vec[i]) st.pop();
		l[i]=st.top();
		st.push(i);
	}
	while(!st.empty()) st.pop();
	st.push(N+1);
	for(int i=N;i>0;i--){
		while(vec[st.top()]>=vec[i]) st.pop();
		r[i]=st.top()-1;
		st.push(i);
	}
	int res=0;
	for(int i=1;i<=N;i++)
		res=max(res,(r[i]-l[i])*vec[i]);
	return res;
	
}
bool check(int md){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(h[i][j]>=md)
				a[i][j]=1;
			else
				a[i][j]=0;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			if(a[i][j])
				a[i][j]+=a[i-1][j];
	}
	area=0;
	for(int i=1;i<=n;i++){
		vector<int> v;
		v.pb(0);
		for(int j=1;j<=m+1;j++){
			v.pb(a[i][j]);
		}
		area=max(area,get_area(v));
	}
	if(area>=k) return 1;
	return 0;
}
void solve(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>h[i][j];
	int l=0,r=1e9;
	int ar=0,ans=0;
	while(r-l>1){
		//cout<<l<<' '<<r<<' ';
		int md=(l+r)/2;
		if(check(md)){
			l=md;
			ans=md,ar=area;
		}
		else
			r=md;
		//cout<<area<<endl;
	}
	cout<<ans<<' '<<ar<<endl;
}
main(){
	//fopn("newbarn");
	//ios;
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}

Compilation message (stderr)

burrow.cpp:90:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   90 | main(){
      | ^~~~
burrow.cpp: In function 'void fopn(std::string)':
burrow.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
burrow.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100