Submission #744467

#	Time	Username	Problem	Language	Result	Execution time	Memory
744467		rainboy	Luxury burrow (IZhO13_burrow)	C11	100 / 100	583 ms	13932 KiB

burrow

#include <stdio.h>
#include <string.h>

#define N	1000
#define M	1000
#define INF	0x3f3f3f3f

int max(int a, int b) { return a > b ? a : b; }

int aa[N][M], n, m;

int solve(int a) {
	static int kk[M], qu[M], ll[M], rr[M];
	int cnt, i, j, ans;

	memset(kk, 0, m * sizeof *kk);
	ans = 0;
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++)
			kk[j] = aa[i][j] >= a ? kk[j] + 1 : 0;
		cnt = 0;
		for (j = 0; j < m; j++) {
			while (cnt && kk[qu[cnt - 1]] >= kk[j])
				cnt--;
			ll[j] = cnt == 0 ? 0 : qu[cnt - 1] + 1;
			qu[cnt++] = j;
		}
		cnt = 0;
		for (j = m - 1; j >= 0; j--) {
			while (cnt && kk[qu[cnt - 1]] > kk[j])
				cnt--;
			rr[j] = cnt == 0 ? m - 1 : qu[cnt - 1] - 1;
			qu[cnt++] = j;
		}
		for (j = 0; j < m; j++)
			ans = max(ans, kk[j] * (rr[j] - ll[j] + 1));
	}
	return ans;
}

int main() {
	int k, i, j, lower, upper, a;

	scanf("%d%d%d", &n, &m, &k);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			scanf("%d", &aa[i][j]);
	lower = 0, upper = INF;
	while (upper - lower > 1) {
		a = (lower + upper) / 2;
		if (solve(a) >= k)
			lower = a;
		else
			upper = a;
	}
	printf("%d %d\n", lower, solve(lower));
	return 0;
}

Compilation message (stderr)

burrow.c: In function 'main':
burrow.c:44:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  scanf("%d%d%d", &n, &m, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
burrow.c:47:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |    scanf("%d", &aa[i][j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100