Submission #4780

#	Time	Username	Problem	Language	Result	Execution time	Memory
4780		tncks0121	Luxury burrow (IZhO13_burrow)	C++98	100 / 100	480 ms	8988 KiB

burrow

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.h>

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int N_ = 1005, M_ = 1005;

int N, M, K;
int A[N_][M_];
int P[N_*M_], PN;
int res1, res2;

int H[M_];

struct state {
	int x, h;
	state(int x = 0, int h = 0): x(x), h(h) { }
};

state Stk[M_];
int tp;

int get (int h) {
	int ret = 0;

	for(int j = 1; j <= M; j++) H[j] = 0;
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= M; j++) if(A[i][j] >= h) ++H[j]; else H[j] = 0;

		tp = 0;

		for(int j = 1; j <= M+1; j++) {
			int x = j;
			while(tp > 0 && Stk[tp].h > H[j]) {
				x = Stk[tp].x;
				ret = max(ret, Stk[tp].h * (j - x));
				--tp;
			}
			if(j <= M && H[j] > 0) {
				Stk[++tp] = state(x, H[j]);
				ret = max(ret, H[j]);
			}
		}
	}

	return ret;
}

int main() {
	int i, j, k;

	scanf("%d%d%d", &N, &M, &K);
	for(i = 1; i <= N; i++) {
		for(j = 1; j <= M; j++) {
			scanf("%d", &A[i][j]);
			P[++PN] = A[i][j];
		}
	}

	sort(P+1, P+PN+1);
	PN = unique(P+1, P+PN+1) - (P+1);

	int low = 1, high = PN;
	while(low <= high) {
		int mid = (low + high) >> 1;
		int area = get(P[mid]);
		if(area >= K) {
			res1 = P[mid]; res2 = area;
			low = mid + 1;
		}else {
			high = mid - 1;
		}
	}

	printf("%d %d\n", res1, res2);
	return 0;
}

• Subtask 1: 100 / 100