Submission #499355

#	Time	Username	Problem	Language	Result	Execution time	Memory
499355		Gurban	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	609 ms	29788 KiB

burrow

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int maxn=1e3+5;
int n,m,k;
int a[maxn][maxn];
int dp[maxn][maxn];
int l[maxn][maxn],r[maxn][maxn];

int f(int val){
	for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) dp[i][j] = (a[i][j] >= val)?dp[i-1][j]+1:0;

	int ans = 0;
	for(int i = 1;i <= n;i++){
		stack<int>S;
		for(int j = 1;j <= m;j++){
			while(!S.empty() and dp[i][S.top()] >= dp[i][j]) S.pop();
			if(!S.empty()) l[i][j] = S.top()+1;
			else l[i][j] = 1;
			S.push(j);
		}
		while(!S.empty()) S.pop();
		for(int j = m;j >= 1;j--){
			while(!S.empty() and dp[i][S.top()] >= dp[i][j]) S.pop();
			if(!S.empty()) r[i][j] = S.top()-1;
			else r[i][j] = m;
			S.push(j);

			ans = max(ans,(r[i][j] - l[i][j] + 1) * dp[i][j]);
		}
	}
	return ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	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 = (int)v.size()-1,md,jog;
	while(l <= r){
		md = (l + r) >> 1;
		if(f(v[md]) >= k) jog=v[md],l=md+1;
		else r=md-1; 
	}
	cout<<jog<<' '<<f(jog);
}

Compilation message (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:54:13: warning: 'jog' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |  cout<<jog<<' '<<f(jog);
      |             ^~~

• Subtask 1: 100 / 100