Submission #47812

#TimeUsernameProblemLanguageResultExecution timeMemory
47812jun6873Luxury burrow (IZhO13_burrow)C++11
0 / 100
2 ms708 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pint; #define x first #define y second int h, w, k, a[1004][1004], c[1004]; int f(int k) { int ans = 0; memset(c, 0, sizeof(c)); for (int i=1; i<=h; i++) { for (int j=1; j<=w; j++) { if (a[i][j] >= k) c[j]++; else c[j] = 0; } stack<pint> st; for (int j=1; j<=w+1; j++) { while (!st.empty() and st.top().x > c[j]) { ans = max(ans, st.top().x * (j - st.top().y)); st.pop(); } st.emplace(c[j], j); } } return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> h >> w >> k; for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) cin >> a[i][j]; int l = 0, r = 1e9 + 2; while (l+1<r) { int m = (l+r)/2; if (f(m) >= k) l = m; else r = m; } cout << l << ' ' << f(l) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...