Submission #518327

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
518327	2022-01-23T11:51:24 Z	ioilolcom	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	1022 ms	18596 KB

burrow

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pii pair<int,int>
#define pb push_back
#define x first
#define y second
#define sz(x) ((int)(x).size())
#define mp make_pair
typedef long long int ll;
int nn,m,k;
const int N=1050;
int g[N][N];
int histogram( vector<int> vv){
	vector<int> a;
	a.push_back(0);
	for(int e:vv) {
		a.push_back(e);
	}
	int n=sz(a)-1;
	vector<int> rt(n+1);
	vector<int> lft(n+1);
	vector<pair<int,int> > v;
	for(int i=1; i<=n; i++) {
		while(sz(v)&&v.back().first>=a[i]) {
			v.pop_back();
		}
		if(sz(v)) {
			lft[i]=v.back().second+1;
		}
		else{
			lft[i]=1;
		}
		v.push_back(mp(a[i],i));
	}
	v.clear();
	for(int i=n; i>=1; i--) {
		while(sz(v)&&v.back().first>=a[i]) {
			v.pop_back();
		}
		if(sz(v)) {
			rt[i]=v.back().second-1;
		}
		else{
			rt[i]=n;
		}
		v.push_back(mp(a[i],i));
	}
	int mx=0;
	for(int i=1; i<=n; i++) {
		mx=max(mx,a[i]*(rt[i]-lft[i]+1));
	}
	return mx;
}
pair<bool,int> check(int x){
	vector<vector<int> > gr(N,vector<int> (N,0));
	for(int i=1; i<=nn; i++) {
		for(int j=1; j<=m; j++) {
			gr[i][j]= (g[i][j]>=x);
		}
	}
	int maxi=0;
	vector<int> dp(N);
	for(int i=1; i<=nn; i++) {
		for(int j=1; j<=m; j++) {
			if(gr[i][j]) {
				dp[j]++;
			}
			else{
				dp[j]=0;
			}
		}
		int ans=histogram(dp);
		maxi=max(maxi,ans);
	}
	return {maxi>=k,maxi};
}
int main()
{

	ios_base:: sync_with_stdio(false); cin.tie(0);
	cin>>nn>>m>>k;
	for(int i=1; i<=nn; i++) {
		for(int j=1; j<=m; j++) {
			cin>>g[i][j];
		}
	}
	int ans=1;
	int area=0;
	int l=1;
	int r=1e9;
	while(l<=r) {
		int mid=(l+r)/2;
		auto info=check(mid);
		if(info.first) {
			if(mid==ans) {
				area=max(area,info.second);
			}
			else{
				ans=mid;
				area=info.second;
			}
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	cout<<ans<<" "<<area<<endl;
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	4776 KB	Output is correct
2	Correct	13 ms	4688 KB	Output is correct
3	Correct	21 ms	4688 KB	Output is correct
4	Correct	25 ms	4688 KB	Output is correct
5	Correct	34 ms	4816 KB	Output is correct
6	Correct	41 ms	4816 KB	Output is correct
7	Correct	15 ms	4732 KB	Output is correct
8	Correct	91 ms	5136 KB	Output is correct
9	Correct	174 ms	5620 KB	Output is correct
10	Correct	178 ms	5820 KB	Output is correct
11	Correct	227 ms	6332 KB	Output is correct
12	Correct	419 ms	6880 KB	Output is correct
13	Correct	102 ms	5456 KB	Output is correct
14	Correct	359 ms	6908 KB	Output is correct
15	Correct	384 ms	6904 KB	Output is correct
16	Correct	366 ms	7408 KB	Output is correct
17	Correct	430 ms	7252 KB	Output is correct
18	Correct	601 ms	10056 KB	Output is correct
19	Correct	662 ms	9420 KB	Output is correct
20	Correct	857 ms	13536 KB	Output is correct
21	Correct	893 ms	14640 KB	Output is correct
22	Correct	1012 ms	18596 KB	Output is correct
23	Correct	1022 ms	18432 KB	Output is correct
24	Correct	900 ms	11460 KB	Output is correct
25	Correct	941 ms	11640 KB	Output is correct