Submission #4765

#	Time	Username	Problem	Language	Result	Execution time	Memory
4765		ainta	Luxury burrow (IZhO13_burrow)	C++98	100 / 100	384 ms	9068 KiB

burrow

#include<stdio.h>
#define N_ 1010
int n, m, k, w[N_][N_], C[N_][N_], i, j, B, E, M, p[N_], st[N_][2], top, R, t, x, Res[2];
int main()
{
	scanf("%d%d%d", &n, &m, &k);
	B = 1;
	for (i = 1; i <= n; i++){
		for (j = 1; j <= m; j++){
			scanf("%d", &w[i][j]);
			if (E < w[i][j])E = w[i][j];
		}
	}
	while (B <= E){
		M = (B + E + 1) >> 1;
		R = 0;
		for (i = 1; i <= m; i++)p[i] = 0;
		for (i = 1; i <= n; i++){
			top = 0;
			for (j = 1; j <= m + 1; j++){
				if (w[i][j] < M)p[j] = i;
				x = j;
				while (top && i - p[j] <= st[top][0]){
					t = st[top][0] * (j - st[top][1]);
					if (R < t)R = t;
					x = st[top][1]; top--;
				}
				if(p[j]!=i)st[++top][0] = i - p[j], st[top][1] = x;
			}
		}
		if (R >= k){
			Res[0] = M, Res[1] = R;
			B = M + 1;
		}
		else E = M - 1;
	}
	printf("%d %d\n", Res[0], Res[1]);
}

• Subtask 1: 100 / 100