#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
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]);
| ^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
6 ms |
696 KB |
Output is correct |
9 |
Correct |
11 ms |
1200 KB |
Output is correct |
10 |
Correct |
24 ms |
1364 KB |
Output is correct |
11 |
Correct |
51 ms |
1880 KB |
Output is correct |
12 |
Correct |
24 ms |
2360 KB |
Output is correct |
13 |
Correct |
37 ms |
1108 KB |
Output is correct |
14 |
Correct |
80 ms |
2356 KB |
Output is correct |
15 |
Correct |
87 ms |
2440 KB |
Output is correct |
16 |
Correct |
94 ms |
2932 KB |
Output is correct |
17 |
Correct |
83 ms |
2764 KB |
Output is correct |
18 |
Correct |
254 ms |
5416 KB |
Output is correct |
19 |
Correct |
288 ms |
4868 KB |
Output is correct |
20 |
Correct |
546 ms |
8988 KB |
Output is correct |
21 |
Correct |
436 ms |
10056 KB |
Output is correct |
22 |
Correct |
541 ms |
13932 KB |
Output is correct |
23 |
Correct |
583 ms |
13876 KB |
Output is correct |
24 |
Correct |
356 ms |
6868 KB |
Output is correct |
25 |
Correct |
357 ms |
6972 KB |
Output is correct |