Submission #250870

#TimeUsernameProblemLanguageResultExecution timeMemory
250870srvltLuxury burrow (IZhO13_burrow)C++14
100 / 100
1223 ms8440 KiB
#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) { int res = 0; for (int j = 1; j <= m; j++) { for (int i = 1; i <= n; i++) dp[i][j] = (a[i][j] >= x) ? (dp[i][j - 1] + 1) : 0; 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 (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:56:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...