답안 #499355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
499355	2021-12-28T04:49:12 Z	Gurban	호화 벙커 (IZhO13_burrow)	C++17	100 / 100	609 ms	29788 KB

burrow

#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

#	결과	실행 시간	메모리	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