# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
118030 | andremfq | Luxury burrow (IZhO13_burrow) | C++17 | 556 ms | 14088 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.
//codigo do Ivan Carvalho
//Busca Binaria no menor valor + Histograma no grid
//N*N*log1000000000 = 3 * 10000000 que passa
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1001;
int matriz[MAXN][MAXN],vetor[MAXN],anterior[MAXN],posterior[MAXN],N,M,K;
int solve(){
vetor[0] = -1;
int ans = 0;
stack<int> pilha;
pilha.push(0);
for(int i = 1;i<=N;i++){
while(vetor[i] < vetor[pilha.top()]){
posterior[pilha.top()] = i;
pilha.pop();
}
if(vetor[pilha.top()] == vetor[i]){
anterior[i] = anterior[pilha.top()];
}
else{
anterior[i] = pilha.top();
}
pilha.push(i);
}
while(!pilha.empty()){
posterior[pilha.top()] = N+1;
pilha.pop();
}
for(int i = 1;i<=N;i++){
anterior[i]++;
posterior[i]--;
ans = max(ans, vetor[i]*(posterior[i] - anterior[i] + 1) );
}
return ans;
}
int func(int val){
int ans = 0;
memset(vetor,0,sizeof(vetor));
for(int coluna = M;coluna>=1;coluna--){
for(int linha = 1;linha<=N;linha++){
int davez = (matriz[linha][coluna] >= val);
if(davez == 0){
vetor[linha] = 0;
}
else{
vetor[linha]++;
}
}
ans = max(ans, solve() );
}
return ans;
}
int main(){
scanf("%d %d %d",&N,&M,&K);
for(int i = 1;i<=N;i++){
for(int j = 1;j<=M;j++){
scanf("%d",&matriz[i][j]);
}
}
int ini = 1,fim = (int)1e9, meio,resp = 0;
while(ini <= fim){
meio = (ini+fim)/2;
if(func(meio) >= K){
resp =meio;
ini = meio + 1;
}
else{
fim = meio - 1;
}
}
printf("%d %d\n",resp,func(resp));
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |