oj.uz

Submission #499355

# Submission time Handle Problem Language Result Execution time Memory
499355 2021-12-28T04:49:12 Z Gurban Luxury burrow (IZhO13_burrow) C++17
100 / 100
 609 ms 29788 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int maxn=1e3+5;
int n,m,k;
int a[maxn][maxn];
int dp[maxn][maxn];
int l[maxn][maxn],r[maxn][maxn];

int f(int val){
	for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) dp[i][j] = (a[i][j] >= val)?dp[i-1][j]+1:0;

	int ans = 0;
	for(int i = 1;i <= n;i++){
		stack<int>S;
		for(int j = 1;j <= m;j++){
			while(!S.empty() and dp[i][S.top()] >= dp[i][j]) S.pop();
			if(!S.empty()) l[i][j] = S.top()+1;
			else l[i][j] = 1;
			S.push(j);
		}
		while(!S.empty()) S.pop();
		for(int j = m;j >= 1;j--){
			while(!S.empty() and dp[i][S.top()] >= dp[i][j]) S.pop();
			if(!S.empty()) r[i][j] = S.top()-1;
			else r[i][j] = m;
			S.push(j);

			ans = max(ans,(r[i][j] - l[i][j] + 1) * dp[i][j]);
		}
	}
	return ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m >> k;
	vector<int>v;
	for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++){
		cin >> a[i][j];
		v.push_back(a[i][j]);
	}
	sort(v.begin(),v.end());
	int l = 0,r = (int)v.size()-1,md,jog;
	while(l <= r){
		md = (l + r) >> 1;
		if(f(v[md]) >= k) jog=v[md],l=md+1;
		else r=md-1; 
	}
	cout<<jog<<' '<<f(jog);
}

Compilation message

burrow.cpp: In function 'int main()':
burrow.cpp:54:13: warning: 'jog' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |  cout<<jog<<' '<<f(jog);
      |             ^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 5 ms 1996 KB Output is correct
9 Correct 11 ms 3788 KB Output is correct
10 Correct 23 ms 4056 KB Output is correct
11 Correct 38 ms 5260 KB Output is correct
12 Correct 30 ms 8660 KB Output is correct
13 Correct 28 ms 2628 KB Output is correct
14 Correct 87 ms 7876 KB Output is correct
15 Correct 98 ms 7904 KB Output is correct
16 Correct 91 ms 8448 KB Output is correct
17 Correct 104 ms 9776 KB Output is correct
18 Correct 235 ms 14020 KB Output is correct
19 Correct 325 ms 15176 KB Output is correct
20 Correct 488 ms 21076 KB Output is correct
21 Correct 441 ms 24044 KB Output is correct
22 Correct 582 ms 29788 KB Output is correct
23 Correct 609 ms 29692 KB Output is correct
24 Correct 511 ms 21132 KB Output is correct
25 Correct 491 ms 22828 KB Output is correct