Submission #118030

#	Time	Username	Problem	Language	Result	Execution time	Memory
118030		andremfq	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	556 ms	14088 KiB

burrow

//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)

burrow.cpp: In function 'int main()':
burrow.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&N,&M,&K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
burrow.cpp:58:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&matriz[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100