Submission #685269

#TimeUsernameProblemLanguageResultExecution timeMemory
685269smartmonkyLuxury burrow (IZhO13_burrow)C++14
100 / 100
1082 ms16284 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define pb push_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define int long long using namespace std; const int N = 2e5 + 5; main(){ int n, m, k; cin >> n >> m >> k; vector < vector <int> > v (n + 1, vector <int> (m + 1)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> v[i][j]; } } int ans = 0; auto check = [&](int x){ vector < vector <int> > p(n + 1, vector <int> (m + 1, 0)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(v[i][j] >= x) p[i][j] = 1 + p[i - 1][j]; } } ans = 0; for(int i = 1; i <= n; i++){ deque <int> q; for(int j = 1 ; j <= m; j++){ int ind = j; while(!q.empty() && p[i][j] <= p[i][q.front()]){ ans = max(ans, p[i][q.front()] * (j - q.front())); p[i][q.front()] = p[i][j]; ind = min(ind, q.front()); q.pop_front(); } q.push_front(ind); } while(!q.empty()){ ans = max(((m + 1) - q.front()) * p[i][q.front()], ans); q.pop_front(); } } return (ans >= k); }; int l = 0, r = 1e9; while(r - l > 1){ int mid = (l + r) >> 1; if(check(mid)){ l = mid; }else r = mid; } check(l); cout << l <<" " << ans; }

Compilation message (stderr)

burrow.cpp:13:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   13 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...