답안 #250866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
250866	2020-07-19T10:20:57 Z	srvlt	호화 벙커 (IZhO13_burrow)	C++14	100 / 100	857 ms	17912 KB

burrow

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 1003;
int n, m, k, a[n0][n0], dp[n0][n0], l[n0], r[n0];
vector <int> v;

int get(int x) {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dp[i][j] = (a[i][j] >= x) ? (dp[i][j - 1] + 1) : 0;
	int res = 0;
	for (int j = 1; j <= m; j++) {
		v.clear();
		for (int i = 1; i <= n; i++) {
			while (!v.empty() && dp[v.back()][j] >= dp[i][j])
				v.pop_back();
			if (v.empty()) l[i] = 1;
			else l[i] = v.back() + 1;
			v.pb(i);
		}
		v.clear();
		for (int i = n; i >= 1; i--) {
			while (!v.empty() && dp[v.back()][j] >= dp[i][j])
				v.pop_back();
			if (v.empty()) r[i] = n;
			else r[i] = v.back() - 1;
			v.pb(i);
			res = max(res, (r[i] - l[i] + 1) * dp[i][j]);
		}
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	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 = (int)1e9 + 1;
	while (l < r - 1) {
		int mid = l + r >> 1;
		if (get(mid) >= k) l = mid;
		else r = mid;
	}
	cout << l << ' ' << get(l);
}

Compilation message

burrow.cpp: In function 'int main()':
burrow.cpp:57:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	512 KB	Output is correct
4	Correct	1 ms	512 KB	Output is correct
5	Correct	1 ms	640 KB	Output is correct
6	Correct	1 ms	640 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	7 ms	1152 KB	Output is correct
9	Correct	13 ms	2048 KB	Output is correct
10	Correct	33 ms	2316 KB	Output is correct
11	Correct	62 ms	2944 KB	Output is correct
12	Correct	33 ms	4480 KB	Output is correct
13	Correct	41 ms	1536 KB	Output is correct
14	Correct	102 ms	4216 KB	Output is correct
15	Correct	113 ms	4096 KB	Output is correct
16	Correct	125 ms	4732 KB	Output is correct
17	Correct	121 ms	4864 KB	Output is correct
18	Correct	320 ms	7928 KB	Output is correct
19	Correct	359 ms	7800 KB	Output is correct
20	Correct	698 ms	12156 KB	Output is correct
21	Correct	633 ms	13688 KB	Output is correct
22	Correct	837 ms	17912 KB	Output is correct
23	Correct	857 ms	17784 KB	Output is correct
24	Correct	493 ms	10752 KB	Output is correct
25	Correct	532 ms	11128 KB	Output is correct