#include "quality.h"
int rectangle(int n, int m, int h, int w, int a[3001][3001]) {
int p[3005][3005];
for (int i = n-1; i >= 0; i--) {
for (int j = m-1; j >= 0; j--) {
a[i+1][j+1] = a[i][j];
}
}
int lo = 1, hi = n*m;
while (lo < hi) {
int mid = (lo + hi) / 2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
p[i][j] = 0;
if (a[i][j] <= mid) p[i][j] = 1;
p[i][j] += p[i-1][j]+p[i][j-1]-p[i-1][j-1];
}
}
int da = 0;
for (int i = h; i <= n; i++) {
for (int j = w; j <= m; j++) {
if (p[i][j]-p[i-h][j]-p[i][j-w]+p[i-h][j-w] > (h*w)/2) {
da = 1;
break;
}
}
if (da) break;
}
if (da) hi = mid;
else lo = mid+1;
}
return lo;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
35752 KB |
Output is correct |
2 |
Correct |
15 ms |
35704 KB |
Output is correct |
3 |
Correct |
15 ms |
35660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
35752 KB |
Output is correct |
2 |
Correct |
15 ms |
35704 KB |
Output is correct |
3 |
Correct |
15 ms |
35660 KB |
Output is correct |
4 |
Correct |
15 ms |
36044 KB |
Output is correct |
5 |
Correct |
15 ms |
35940 KB |
Output is correct |
6 |
Correct |
16 ms |
36012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
35752 KB |
Output is correct |
2 |
Correct |
15 ms |
35704 KB |
Output is correct |
3 |
Correct |
15 ms |
35660 KB |
Output is correct |
4 |
Correct |
15 ms |
36044 KB |
Output is correct |
5 |
Correct |
15 ms |
35940 KB |
Output is correct |
6 |
Correct |
16 ms |
36012 KB |
Output is correct |
7 |
Correct |
39 ms |
37152 KB |
Output is correct |
8 |
Correct |
30 ms |
37100 KB |
Output is correct |
9 |
Correct |
29 ms |
37144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
35752 KB |
Output is correct |
2 |
Correct |
15 ms |
35704 KB |
Output is correct |
3 |
Correct |
15 ms |
35660 KB |
Output is correct |
4 |
Correct |
15 ms |
36044 KB |
Output is correct |
5 |
Correct |
15 ms |
35940 KB |
Output is correct |
6 |
Correct |
16 ms |
36012 KB |
Output is correct |
7 |
Correct |
39 ms |
37152 KB |
Output is correct |
8 |
Correct |
30 ms |
37100 KB |
Output is correct |
9 |
Correct |
29 ms |
37144 KB |
Output is correct |
10 |
Correct |
255 ms |
43536 KB |
Output is correct |
11 |
Correct |
222 ms |
43532 KB |
Output is correct |
12 |
Correct |
128 ms |
41472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
35752 KB |
Output is correct |
2 |
Correct |
15 ms |
35704 KB |
Output is correct |
3 |
Correct |
15 ms |
35660 KB |
Output is correct |
4 |
Correct |
15 ms |
36044 KB |
Output is correct |
5 |
Correct |
15 ms |
35940 KB |
Output is correct |
6 |
Correct |
16 ms |
36012 KB |
Output is correct |
7 |
Correct |
39 ms |
37152 KB |
Output is correct |
8 |
Correct |
30 ms |
37100 KB |
Output is correct |
9 |
Correct |
29 ms |
37144 KB |
Output is correct |
10 |
Correct |
255 ms |
43536 KB |
Output is correct |
11 |
Correct |
222 ms |
43532 KB |
Output is correct |
12 |
Correct |
128 ms |
41472 KB |
Output is correct |
13 |
Correct |
2185 ms |
70836 KB |
Output is correct |
14 |
Correct |
2238 ms |
70924 KB |
Output is correct |
15 |
Correct |
2021 ms |
70844 KB |
Output is correct |