oj.uz

Submission #537992

# Submission time Handle Problem Language Result Execution time Memory
537992 2022-03-16T02:10:26 Z GioChkhaidze Luxury burrow (IZhO13_burrow) C++14
100 / 100
 394 ms 17932 KB 
#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

const int N = 1003;

int n, m, k, ans_c, ans_a, a[N][N], b[N][N];

bool check(int x) {
	for (int i = n; i >= 1; --i)
		for (int j = m; j >= 1; --j) 
			if (a[i][j] >= x) b[i][j] = b[i + 1][j] + 1;
				else b[i][j] = 0;

	int area = 0;
	deque < pair < int , int > > dq;
	for (int i = 1; i <= n; ++i) {
		for (int j = m; j >= 1; --j) {
			int id = j;
			while (dq.size() && dq.back().f >= b[i][j]) {	
				area = max(area, dq.back().f * (dq.back().s - j));
				id = dq.back().s;
				dq.pop_back();
			}
			area = max(area, b[i][j] * (id - j + 1));
			dq.push_back({b[i][j], id});
		}
		while (dq.size()) {
			area = max(area, dq.back().f * dq.back().s);
			dq.pop_back();
		}
	}		
			
	if (area >= k) {
		ans_c = x;
		ans_a = area;
		return true;
	}
	return false;
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) 
			cin >> a[i][j];
	
	int l = 1, r = 1e9, mid;
	while (l <= r) {
		mid = ((l + r) >> 1);
		if (check(mid))
			l = mid + 1;
				else
			r = mid - 1;
	}
	cout << ans_c << " " << ans_a << "\n";
}

Compilation message

burrow.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main () {
      | ^~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 4 ms 1108 KB Output is correct
9 Correct 11 ms 2016 KB Output is correct
10 Correct 23 ms 2132 KB Output is correct
11 Correct 31 ms 2892 KB Output is correct
12 Correct 24 ms 4304 KB Output is correct
13 Correct 22 ms 1436 KB Output is correct
14 Correct 55 ms 4044 KB Output is correct
15 Correct 64 ms 4040 KB Output is correct
16 Correct 65 ms 4544 KB Output is correct
17 Correct 64 ms 4692 KB Output is correct
18 Correct 156 ms 7704 KB Output is correct
19 Correct 180 ms 7636 KB Output is correct
20 Correct 310 ms 12172 KB Output is correct
21 Correct 362 ms 13516 KB Output is correct
22 Correct 394 ms 17932 KB Output is correct
23 Correct 386 ms 17844 KB Output is correct
24 Correct 275 ms 10568 KB Output is correct
25 Correct 287 ms 11084 KB Output is correct