oj.uz

Submission #388287

# Submission time Handle Problem Language Result Execution time Memory
388287 2021-04-10T18:58:41 Z ritul_kr_singh Luxury burrow (IZhO13_burrow) C++17
100 / 100
 416 ms 17840 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

int n, m, k, g[1001][1001], a[1002];

int maxArea(){
	int res = 0;
	vector<int> st = {0};
	for(int j=1; j<=m+1; ++j){
		while(!st.empty() and a[st.back()] > a[j]){
			int y = a[st.back()]; st.pop_back();
			res = max(res, (j-st.back()-1)*y);
		}
		st.push_back(j);
	}
	return res;
}

int best(int x){
	fill(a, a+m+2, 0LL);
	int res = 0;
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=m; ++j)
			a[j] += g[i][j] >= x ? 1 : -a[j];
		res = max(res, maxArea());
	}
	return res;
}


signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> k;
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=m; ++j)
			cin >> g[i][j];
	int low = 0, high = 1e9;
	while(low<high){
		int mid = (low+high)/2;
		if(best(mid+1)>=k) low = mid+1;
		else high = mid;
	}
	cout << low sp best(low);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 4 ms 716 KB Output is correct
9 Correct 8 ms 1284 KB Output is correct
10 Correct 23 ms 1420 KB Output is correct
11 Correct 35 ms 1740 KB Output is correct
12 Correct 27 ms 2636 KB Output is correct
13 Correct 26 ms 1484 KB Output is correct
14 Correct 55 ms 3644 KB Output is correct
15 Correct 57 ms 3732 KB Output is correct
16 Correct 61 ms 4196 KB Output is correct
17 Correct 65 ms 4664 KB Output is correct
18 Correct 153 ms 7812 KB Output is correct
19 Correct 170 ms 7616 KB Output is correct
20 Correct 320 ms 12100 KB Output is correct
21 Correct 301 ms 13764 KB Output is correct
22 Correct 389 ms 17840 KB Output is correct
23 Correct 416 ms 17804 KB Output is correct
24 Correct 259 ms 10572 KB Output is correct
25 Correct 276 ms 11012 KB Output is correct