Submission #499355

#TimeUsernameProblemLanguageResultExecution timeMemory
499355GurbanLuxury burrow (IZhO13_burrow)C++17
100 / 100
609 ms29788 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int maxn=1e3+5; int n,m,k; int a[maxn][maxn]; int dp[maxn][maxn]; int l[maxn][maxn],r[maxn][maxn]; int f(int val){ for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) dp[i][j] = (a[i][j] >= val)?dp[i-1][j]+1:0; int ans = 0; for(int i = 1;i <= n;i++){ stack<int>S; for(int j = 1;j <= m;j++){ while(!S.empty() and dp[i][S.top()] >= dp[i][j]) S.pop(); if(!S.empty()) l[i][j] = S.top()+1; else l[i][j] = 1; S.push(j); } while(!S.empty()) S.pop(); for(int j = m;j >= 1;j--){ while(!S.empty() and dp[i][S.top()] >= dp[i][j]) S.pop(); if(!S.empty()) r[i][j] = S.top()-1; else r[i][j] = m; S.push(j); ans = max(ans,(r[i][j] - l[i][j] + 1) * dp[i][j]); } } return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> k; vector<int>v; for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++){ cin >> a[i][j]; v.push_back(a[i][j]); } sort(v.begin(),v.end()); int l = 0,r = (int)v.size()-1,md,jog; while(l <= r){ md = (l + r) >> 1; if(f(v[md]) >= k) jog=v[md],l=md+1; else r=md-1; } cout<<jog<<' '<<f(jog); }

Compilation message (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:54:13: warning: 'jog' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |  cout<<jog<<' '<<f(jog);
      |             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...