oj.uz

답안 #4760

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4760 2014-01-01T08:09:55 Z cki86201 호화 벙커 (IZhO13_burrow) C++
100 / 100
 916 ms 9176 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

int n,m,k,ans2;
int inp[1010][1010];
int tmp[1010][1010];

typedef pair<int,int> Pi;
#define X first
#define Y second

vector <Pi> v;

bool check(int x)
{
	int i,j;
	for(i=0;i<n;i++){
		tmp[i][0]=(inp[i][0]>=x);
		for(j=1;j<m;j++)
			if(inp[i][j]>=x)tmp[i][j]=tmp[i][j-1]+1;
			else tmp[i][j]=0;
	}
	int mx = 0;
	for(j=0;j<m;j++){
		v.clear();
		for(i=0;i<=n;i++){
			int a = i;
			while(!v.empty() && v.back().Y >= tmp[i][j]){
				a=v.back().X;
				mx = max(mx,v.back().Y * (i - a));
				v.pop_back();
			}
			v.push_back(Pi(a,tmp[i][j]));
		}
	}
	if(mx>=k){ans2=mx;return true;}
	return false;
}

int main(){
	scanf("%d%d%d",&n,&m,&k);
	int i,j;
	for(i=0;i<n;i++){
		for(j=0;j<m;j++)scanf("%d",inp[i]+j);
	}
	int st=1,en=1e9,mi,ans;
	while(st<=en){
		mi = (st+en)>>1;
		if(check(mi))st=mi+1,ans=mi;
		else en=mi-1;
	}
	printf("%d %d",ans,ans2);
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 9176 KB Output is correct
2 Correct 0 ms 9176 KB Output is correct
3 Correct 0 ms 9176 KB Output is correct
4 Correct 0 ms 9176 KB Output is correct
5 Correct 0 ms 9176 KB Output is correct
6 Correct 0 ms 9176 KB Output is correct
7 Correct 0 ms 9176 KB Output is correct
8 Correct 4 ms 9176 KB Output is correct
9 Correct 8 ms 9176 KB Output is correct
10 Correct 28 ms 9176 KB Output is correct
11 Correct 48 ms 9176 KB Output is correct
12 Correct 32 ms 9176 KB Output is correct
13 Correct 36 ms 9176 KB Output is correct
14 Correct 108 ms 9176 KB Output is correct
15 Correct 112 ms 9176 KB Output is correct
16 Correct 116 ms 9176 KB Output is correct
17 Correct 156 ms 9176 KB Output is correct
18 Correct 276 ms 9176 KB Output is correct
19 Correct 384 ms 9176 KB Output is correct
20 Correct 664 ms 9176 KB Output is correct
21 Correct 704 ms 9176 KB Output is correct
22 Correct 896 ms 9176 KB Output is correct
23 Correct 916 ms 9176 KB Output is correct
24 Correct 604 ms 9176 KB Output is correct
25 Correct 740 ms 9176 KB Output is correct