Submission #1279606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279606		SmuggingSpun	Luxury burrow (IZhO13_burrow)	C++20	100 / 100	509 ms	8320 KiB

burrow

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
const int lim = 1e3 + 5;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
int n, m, k, a[lim][lim], f[lim][lim];
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	pair<int, int>ans;
	int low = 1, high = 1e9;
	while(low <= high){
		int mid = (low + high) >> 1;
		for(int i = max(n, m); i > 0; i--){
			f[i][0] = 0;
		}
		fill(f[0], f[0] + max(n, m) + 1, 0);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				f[i][j] = (a[i][j] < mid ? 0 : f[i][j - 1] + 1);
			}
		}
		int area = 0;
		for(int j = 1; j <= m; j++){
			vector<int>u(n + 1);
			stack<int>st;
			for(int i = 1; i <= n; st.push(i++)){
				while(!st.empty() && f[st.top()][j] >= f[i][j]){
					st.pop();
				}
				u[i] = (st.empty() ? 0 : st.top());
			}
			while(!st.empty()){
				st.pop();
			}
			for(int i = n; i > 0; st.push(i--)){
				while(!st.empty() && f[st.top()][j] >= f[i][j]){
					st.pop();
				}
				maximize(area, ((st.empty() ? n : st.top() - 1) - u[i]) * f[i][j]);
			}
		}
		if(area >= k){
			ans = make_pair(mid, area);
			low = mid + 1;
		}
		else{
			high = mid - 1;
		}
	}
	cout << ans.first << " " << ans.second;
}

Compilation message (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:14:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100