oj.uz

답안 #5398

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5398 2014-04-30T10:00:16 Z gs12117 호화 벙커 (IZhO13_burrow) C++
100 / 100
 648 ms 5088 KB 
#include<stdio.h>
int n,m,p;
int a[1010][1010];
int b[1010];
int stk[1010];
int sp;
int lend[1010];
int rend[1010];
int f(int x){
	int i,j,ans;
	for(i=0;i<m;i++){
		b[i]=0;
	}
	ans=0;
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			if(a[i][j]>=x){
				b[j]++;
			}
			else b[j]=0;
		}
		stk[0]=-1;
		sp=1;
		for(j=0;j<m;j++){
			while(sp!=1&&b[stk[sp-1]]>=b[j])sp--;
			lend[j]=stk[sp-1];
			stk[sp]=j;
			sp++;
		}
		stk[0]=m;
		sp=1;
		for(j=m-1;j>=0;j--){
			while(sp!=1&&b[stk[sp-1]]>=b[j])sp--;
			rend[j]=stk[sp-1];
			stk[sp]=j;
			sp++;
		}
		for(j=0;j<m;j++){
			if(ans<b[j]*(rend[j]-lend[j]-1))ans=b[j]*(rend[j]-lend[j]-1);
		}
	}
	return ans;
}
int main(){
	int i,j;
	scanf("%d%d%d",&n,&m,&p);
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			scanf("%d",&a[i][j]);
		}
	}
	j=-1;
	for(i=30;i>=0;i--){
		j+=1<<i;
		if(f(j)<p)j-=1<<i;
	}
	printf("%d %d",j,f(j));
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5088 KB Output is correct
2 Correct 0 ms 5088 KB Output is correct
3 Correct 0 ms 5088 KB Output is correct
4 Correct 0 ms 5088 KB Output is correct
5 Correct 0 ms 5088 KB Output is correct
6 Correct 0 ms 5088 KB Output is correct
7 Correct 0 ms 5088 KB Output is correct
8 Correct 4 ms 5088 KB Output is correct
9 Correct 12 ms 5088 KB Output is correct
10 Correct 28 ms 5088 KB Output is correct
11 Correct 56 ms 5088 KB Output is correct
12 Correct 24 ms 5088 KB Output is correct
13 Correct 40 ms 5088 KB Output is correct
14 Correct 84 ms 5088 KB Output is correct
15 Correct 88 ms 5088 KB Output is correct
16 Correct 92 ms 5088 KB Output is correct
17 Correct 104 ms 5088 KB Output is correct
18 Correct 260 ms 5088 KB Output is correct
19 Correct 300 ms 5088 KB Output is correct
20 Correct 640 ms 5088 KB Output is correct
21 Correct 520 ms 5088 KB Output is correct
22 Correct 636 ms 5088 KB Output is correct
23 Correct 648 ms 5088 KB Output is correct
24 Correct 464 ms 5088 KB Output is correct
25 Correct 444 ms 5088 KB Output is correct