Submission #1192707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192707		nuutsnoynton	Luxury burrow (IZhO13_burrow)	C++20	0 / 100	0 ms	320 KiB

burrow

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll a[1002][1002], b[1002][1002], hevtee[1002][1002], bosoo[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(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 ++) {
				hevtee[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) {
					hevtee[i][j] = hevtee[i][j - 1] + 1;
					bosoo[i][j] = bosoo[i - 1][j] + 1;
				}
				else {
					hevtee[i][j] = bosoo[i][j] = 0;
				}
				s = max(s, hevtee[i][j] * bosoo[i][j]);
			}
		}
		if ( s >= area) lo = mid + 1;
		else hi = mid;
	}
	lo --;
	for (i = 1; i <= n; i ++) {
			for (j = 1; j <= m; j ++) {
				hevtee[i][j] = 0;
				bosoo[i][j] = 0;
				if ( a[i][j] >= v[lo]) 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) {
					hevtee[i][j] = hevtee[i][j - 1] + 1;
					bosoo[i][j] = bosoo[i - 1][j] + 1;
				}
				else {
					hevtee[i][j] = bosoo[i][j] = 0;
				}
				s = max(s, hevtee[i][j] * bosoo[i][j]);
			}
		}
	cout << v[lo] << " " << s <<" " << endl;
}

• Subtask 1: 0 / 100