Submission #81819

#TimeUsernameProblemLanguageResultExecution timeMemory
81819mra2322001Luxury burrow (IZhO13_burrow)C++14
0 / 100
2 ms512 KiB
#include <bits/stdc++.h> #define f0(i, n) for(int i(0); i < (n); i++) #define f1(i, n) for(int i(1); i <= n; i++) using namespace std; typedef long long ll; const int N = 402; int n, k, a[N][N], m, l[N], r[N], b[N], cur = 0; vector <int> v; bool check(int x){ f1(i, n) b[i] = 0; int res = 0; stack <int> s; f1(i, m){ f1(j, n){ if(a[i][j] >= x) b[j]++; else b[j] = 0; } f1(j, n){ while(s.size() && b[s.top()] >= b[j]) s.pop(); if(s.size()) l[j] = s.top() + 1; else l[j] = 1; s.push(j); } while(s.size()) s.pop(); for(int j = n; j >= 1; j--){ while(s.size() && b[s.top()] >= b[j]) s.pop(); if(s.size()) r[j] = s.top() - 1; else r[j] = n; s.push(j); } f1(j, n){ res = max(res, (r[j] - l[j] + 1)*b[j]); } } if(res >= k){ cur = res; return 1; } return 0; } int main(){ ios_base::sync_with_stdio(0); cin >> m >> n >> k; f1(i, m) f1(j, n) { cin >> a[i][j]; v.emplace_back(a[i][j]); } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); int l = 0, r = v.size() - 1, ans = 0; while(l <= r){ int mid = (l + r)/2; if(check(v[mid])) l = mid + 1, ans = mid; else r = mid - 1; } cout << v[ans] << " " << cur; }
#Verdict Execution timeMemoryGrader output
Fetching results...