# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
499355 | Gurban | Luxury burrow (IZhO13_burrow) | C++17 | 609 ms | 29788 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |