Submission #1118907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118907		Tsagana	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	344 ms	34128 KiB

burrow

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int n, m, k;
int a[1001][1001];
int b[1001][1001];
vector<int> v;
pair<int, int> ans;

bool find(int x) {
	bool id = 0;
	int s = 0;
	int l[1001];
	int r[1001];

	for (int i = n; i >= 1; i--)
	for (int j = 1; j <= m; j++)
		b[i][j] = (a[i][j] < x ? 0 : b[i+1][j]+1);
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			l[j] = j-1;
			while (l[j] >= 1 && b[i][j] <= b[i][l[j]]) l[j] = l[l[j]];
		}
		for (int j = m; j >= 1; j--) {
			r[j] = j+1;
			while (r[j] <= m && b[i][j] <= b[i][r[j]]) r[j] = r[r[j]];
			
			s = max(s, (b[i][j] * (r[j] - l[j] - 1)));
		}
	}
	if (s >= k) id = 1;

	if (id && (ans.F < x || (ans.F == x && ans.S < s))) ans = {x, s};
	return id;
}

void search() {
	int l = 0, r = v.size()-1;

	while (l <= r) {
		int M = (l + r) / 2;
		
		if (find(v[M])) l = M+1;
		else r = M-1;
	}
}

void solve () {
	cin >> n >> m >> k;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			v.pb(a[i][j]);
		}
	}

	sort(all(v));
	search();
	
	cout << ans.F << ' ' << ans.S;
}
signed main() {IOS solve(); return 0;}

• Subtask 1: 100 / 100