답안 #388288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
388288	2021-04-10T19:01:47 Z	ritul_kr_singh	호화 벙커 (IZhO13_burrow)	C++17	100 / 100	399 ms	8260 KB

burrow

#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 x = 0;
	for(int y=1<<30; y; y/=2)
		if(best(x+y)>=k) x += y;
	cout << x sp best(x);
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	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	5 ms	812 KB	Output is correct
9	Correct	9 ms	1228 KB	Output is correct
10	Correct	20 ms	1432 KB	Output is correct
11	Correct	31 ms	1740 KB	Output is correct
12	Correct	21 ms	2724 KB	Output is correct
13	Correct	25 ms	1100 KB	Output is correct
14	Correct	55 ms	3164 KB	Output is correct
15	Correct	57 ms	3148 KB	Output is correct
16	Correct	61 ms	3104 KB	Output is correct
17	Correct	65 ms	4128 KB	Output is correct
18	Correct	157 ms	5000 KB	Output is correct
19	Correct	181 ms	5828 KB	Output is correct
20	Correct	324 ms	6468 KB	Output is correct
21	Correct	305 ms	7492 KB	Output is correct
22	Correct	395 ms	8156 KB	Output is correct
23	Correct	399 ms	8260 KB	Output is correct
24	Correct	273 ms	7792 KB	Output is correct
25	Correct	290 ms	8144 KB	Output is correct