oj.uz

Submission #250872

# Submission time Handle Problem Language Result Execution time Memory
250872 2020-07-19T10:27:55 Z srvlt Luxury burrow (IZhO13_burrow) C++14
100 / 100
 755 ms 4344 KB 
#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

# Verdict Execution time Memory 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