Submission #41315

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
41315	2018-02-15T21:41:10 Z	IvanC	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	622 ms	50652 KB

burrow

#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

burrow.cpp: In function 'int main()':
burrow.cpp:52:28: 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:55:29: 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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	540 KB	Output is correct
4	Correct	2 ms	632 KB	Output is correct
5	Correct	2 ms	732 KB	Output is correct
6	Correct	2 ms	748 KB	Output is correct
7	Correct	3 ms	768 KB	Output is correct
8	Correct	6 ms	1136 KB	Output is correct
9	Correct	10 ms	1696 KB	Output is correct
10	Correct	28 ms	1960 KB	Output is correct
11	Correct	49 ms	2928 KB	Output is correct
12	Correct	25 ms	3916 KB	Output is correct
13	Correct	38 ms	3916 KB	Output is correct
14	Correct	76 ms	4624 KB	Output is correct
15	Correct	81 ms	5192 KB	Output is correct
16	Correct	90 ms	6400 KB	Output is correct
17	Correct	102 ms	7128 KB	Output is correct
18	Correct	204 ms	10332 KB	Output is correct
19	Correct	248 ms	12612 KB	Output is correct
20	Correct	454 ms	18680 KB	Output is correct
21	Correct	480 ms	25224 KB	Output is correct
22	Correct	622 ms	35392 KB	Output is correct
23	Correct	616 ms	45072 KB	Output is correct
24	Correct	422 ms	47544 KB	Output is correct
25	Correct	514 ms	50652 KB	Output is correct