Submission #1355566

#TimeUsernameProblemLanguageResultExecution timeMemory
1355566Chinguun호화 벙커 (IZhO13_burrow)C++20
100 / 100
229 ms16220 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define meta int tm = (tl + tr) / 2, x = i * 2 + 1, y = x + 1

const int SN = 1007;
const int TN = 4 * SN;
const int oo = 1e18;
const int mod = 1e9 + 7;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;

int n, m, k, mx;
int a[SN][SN], b[SN][SN], h[SN];

int find () {
	stack<int> st;
	st.push(0);
	int MX = 0;
	for (int i = 1; i <= m + 1; i++) {
		while (h[st.top()] >= h[i]) {
			int last = st.top();
			st.pop();
			int area = h[last] * (i - st.top() - 1);
			if (area > MX) MX = area;
		}
		st.push(i);
	}
	return MX;
}

int solve (int x) {
	for (int i = 1; i <= m; i++) {
		h[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] >= x) b[i][j] = 1;
			else b[i][j] = 0;
			// cout << b[i][j] << ' ';
		}
		// cout << '\n';
	}
	mx = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (h[j]) h[j]--;
			else {
				int cnt = 0;
				while (b[i + cnt][j]) cnt++;
				h[j] = cnt;
			}
		}
		// for (int i = 1; i <= m; i++) {
		// 	cout << h[i] << ' ';
		// } cout << '\n';
		int s = find();
		if (s > mx) mx = s;
	}
	if (mx >= k) return 1;
	return 0;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	h[0] = -1;
	int l = 1, r = 1e9;
	while (l < r) {
		int m = (l + r) / 2;
		// cout << m << '\n';
		int t = solve(m);
		if (t == 1) l = m + 1;
		else r = m;
	}
	solve(r - 1);
	cout << r - 1 << ' ' << mx;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...