답안 #250872

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
250872	2020-07-19T10:27:55 Z	srvlt	호화 벙커 (IZhO13_burrow)	C++14	100 / 100	755 ms	4344 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], l[n0], r[n0];
vector <int> v;

int get(int x) {
	int res = 0;
	memset(& dp, 0, sizeof(dp));
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n; i++)
			dp[i] = (a[i][j] >= x) ? (dp[i] + 1) : 0;
		v.clear();
		for (int i = 1; i <= n; i++) {
			while (!v.empty() && dp[v.back()] >= dp[i])
				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()] >= dp[i])
				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]);
		}
	}
	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	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	512 KB	Output is correct
6	Correct	1 ms	512 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	6 ms	768 KB	Output is correct
9	Correct	11 ms	1152 KB	Output is correct
10	Correct	30 ms	1196 KB	Output is correct
11	Correct	54 ms	1280 KB	Output is correct
12	Correct	33 ms	2424 KB	Output is correct
13	Correct	40 ms	768 KB	Output is correct
14	Correct	94 ms	1920 KB	Output is correct
15	Correct	98 ms	1920 KB	Output is correct
16	Correct	105 ms	1920 KB	Output is correct
17	Correct	109 ms	2304 KB	Output is correct
18	Correct	281 ms	2680 KB	Output is correct
19	Correct	305 ms	3152 KB	Output is correct
20	Correct	620 ms	3704 KB	Output is correct
21	Correct	568 ms	3960 KB	Output is correct
22	Correct	680 ms	4344 KB	Output is correct
23	Correct	755 ms	4344 KB	Output is correct
24	Correct	495 ms	4144 KB	Output is correct
25	Correct	536 ms	4344 KB	Output is correct