Submission #388286

#	Time	Username	Problem	Language	Result	Execution time	Memory
388286		ritul_kr_singh	Luxury burrow (IZhO13_burrow)	C++17	0 / 100	34 ms	3080 KiB

burrow

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

int n, m, k, g[401][401], a[402];

int maxArea(){
	int res = 0;
	vector<int> st = {0};
	for(int j=1; j<=m+1; ++j){
		while(!st.empty() and a[st.back()] > a[j]){
			int y = a[st.back()]; st.pop_back();
			res = max(res, (j-st.back()-1)*y);
		}
		st.push_back(j);
	}
	return res;
}

int best(int x){
	fill(a, a+m+2, 0LL);
	int res = 0;
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=m; ++j)
			a[j] += g[i][j] >= x ? 1 : -a[j];
		res = max(res, maxArea());
	}
	return res;
}


signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> k;
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=m; ++j)
			cin >> g[i][j];
	int low = 0, high = 1e9;
	while(low<high){
		int mid = (low+high)/2;
		if(best(mid+1)>=k) low = mid+1;
		else high = mid;
	}
	cout << low sp best(low);
}

• Subtask 1: 0 / 100