Submission #1192716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192716		nuutsnoynton	Luxury burrow (IZhO13_burrow)	C++20	100 / 100	616 ms	47640 KiB

burrow

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair < ll, ll > ;

ll a[1002][1002], b[1002][1002], lef[1002][1002], bosoo[1002][1002], rig[1002][1002];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll n, m, area, lo, hi, mid, i, j, s;
	
	cin >> n >> m >> area;
	
	vector < ll > v;	
	for (i = 1; i <= n; i ++) {
		for (j = 1; j <= m; j ++) {
			cin >> a[i][j];
			v.push_back(a[i][j]);
		}
	}
	v.push_back(0);
	v.push_back(1e9 + 1);
	sort(v.begin(), v.end());
	
	lo = 0;
	hi = v.size();
	
	while ( lo < hi) {
		mid = (lo + hi)/2;
		
		for (i = 1; i <= n; i ++) {
			for (j = 1; j <= m; j ++) {
				lef[i][j] = rig[i][j] = 0;
				bosoo[i][j] = 0;
				if ( a[i][j] >= v[mid]) b[i][j] = 1;
				else b[i][j] = 0;
			}
		}
		s = 0;
		for (i = 1; i <= n; i ++) {
			for (j = 1; j <= m; j ++) {
				if ( b[i][j] == 1) {
					bosoo[i][j] = bosoo[i - 1][j] + 1;
				}
				else {
					bosoo[i][j] = 0;
				}
			}
		}
		for (i = 1; i <= n; i ++) {
			stack < pll > S;
			S.push(make_pair(-1, 0));
			for (j = 1; j <= m; j ++) {
				while(S.top().first >= bosoo[i][j]) S.pop();
				lef[i][j] = S.top().second;
				S.push(make_pair(bosoo[i][j], j));
			}
		}
		for (i = 1; i <= n; i ++) {
			stack < pll > S;
			S.push(make_pair(-1, m + 1));
			for (j = m; j >= 1; j --) {
				while(S.top().first >= bosoo[i][j]) S.pop();
				rig[i][j] = S.top().second;
				S.push(make_pair(bosoo[i][j], j));
			}
		}
		for (i = 1; i <= n; i ++) {
			for (j = 1; j <= m; j ++) {
				s = max(s, (rig[i][j] - lef[i][j] - 1) * bosoo[i][j]);
			}
		}
		if ( s >= area) lo = mid + 1;
		else hi = mid;
	}
	lo --;
	mid = lo;
	for (i = 1; i <= n; i ++) {
		for (j = 1; j <= m; j ++) {
			lef[i][j] = rig[i][j] = 0;
			bosoo[i][j] = 0;
			if ( a[i][j] >= v[mid]) b[i][j] = 1;
			else b[i][j] = 0;
		}
	}
	s = 0;
	for (i = 1; i <= n; i ++) {
		for (j = 1; j <= m; j ++) {
			if ( b[i][j] == 1) {
				bosoo[i][j] = bosoo[i - 1][j] + 1;
			}
			else {
				bosoo[i][j] = 0;
			}
		}
	}
	for (i = 1; i <= n; i ++) {
		stack < pll > S;
		S.push(make_pair(-1, 0));
		for (j = 1; j <= m; j ++) {
			while(S.top().first >= bosoo[i][j]) S.pop();
			lef[i][j] = S.top().second;
			S.push(make_pair(bosoo[i][j], j));
		}
	}
	for (i = 1; i <= n; i ++) {
		stack < pll > S;
		S.push(make_pair(-1, m + 1));
		for (j = m; j >= 1; j --) {
			while(S.top().first >= bosoo[i][j]) S.pop();
			rig[i][j] = S.top().second ;
			S.push(make_pair(bosoo[i][j], j));
		}
	}
	for (i = 1; i <= n; i ++) {
		for (j = 1; j <= m; j ++) {
			s = max(s, (rig[i][j] - lef[i][j] - 1) * bosoo[i][j]);
		}
	}
	cout << v[lo] << " " << s <<" " << endl;
}

• Subtask 1: 100 / 100