#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int r, c, h, w, q[3001][3001];
int add[3001][3001];
bool good()
{
for (int i = 0; i + h - 1 < r; i++)
{
for (int j = 0; j + w - 1 < c; j++)
{
int sum = add[i + h - 1][j + w - 1];
if (i != 0) sum -= add[i - 1][j + w - 1];
if (j != 0) sum -= add[i + h - 1][j - 1];
if (i != 0 && j != 0) sum += add[i - 1][j - 1];
if (sum >= (h * w - 1) / 2 + 1) return true;
}
}
return false;
}
void make(int num)
{
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++) add[i][j] = 0;
}
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
if (q[i][j] <= num) add[i][j] = 1;
if (i != 0) add[i][j] += add[i - 1][j];
if (j != 0) add[i][j] += add[i][j - 1];
if (i != 0 && j != 0) add[i][j] -= add[i - 1][j - 1];
}
}
}
int bs()
{
int a = 0;
int b = r * c;
int res = -1;
while (a <= b)
{
int mid = (a + b) / 2;
make(mid);
if (good())
{
res = mid;
b = mid - 1;
} else a = mid + 1;
}
return res;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
r = R;
c = C;
h = H;
w = W;
for (int i = 0; i < 3001; i++)
{
for (int j = 0; j < 3001; j++) q[i][j] = Q[i][j];
}
return bs();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
35948 KB |
Output is correct |
2 |
Correct |
29 ms |
35820 KB |
Output is correct |
3 |
Correct |
35 ms |
35820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
35948 KB |
Output is correct |
2 |
Correct |
29 ms |
35820 KB |
Output is correct |
3 |
Correct |
35 ms |
35820 KB |
Output is correct |
4 |
Correct |
34 ms |
36480 KB |
Output is correct |
5 |
Correct |
31 ms |
36460 KB |
Output is correct |
6 |
Correct |
31 ms |
36460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
35948 KB |
Output is correct |
2 |
Correct |
29 ms |
35820 KB |
Output is correct |
3 |
Correct |
35 ms |
35820 KB |
Output is correct |
4 |
Correct |
34 ms |
36480 KB |
Output is correct |
5 |
Correct |
31 ms |
36460 KB |
Output is correct |
6 |
Correct |
31 ms |
36460 KB |
Output is correct |
7 |
Correct |
51 ms |
38764 KB |
Output is correct |
8 |
Correct |
51 ms |
38764 KB |
Output is correct |
9 |
Correct |
50 ms |
38764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
35948 KB |
Output is correct |
2 |
Correct |
29 ms |
35820 KB |
Output is correct |
3 |
Correct |
35 ms |
35820 KB |
Output is correct |
4 |
Correct |
34 ms |
36480 KB |
Output is correct |
5 |
Correct |
31 ms |
36460 KB |
Output is correct |
6 |
Correct |
31 ms |
36460 KB |
Output is correct |
7 |
Correct |
51 ms |
38764 KB |
Output is correct |
8 |
Correct |
51 ms |
38764 KB |
Output is correct |
9 |
Correct |
50 ms |
38764 KB |
Output is correct |
10 |
Correct |
317 ms |
51516 KB |
Output is correct |
11 |
Correct |
308 ms |
58220 KB |
Output is correct |
12 |
Correct |
169 ms |
51052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
35948 KB |
Output is correct |
2 |
Correct |
29 ms |
35820 KB |
Output is correct |
3 |
Correct |
35 ms |
35820 KB |
Output is correct |
4 |
Correct |
34 ms |
36480 KB |
Output is correct |
5 |
Correct |
31 ms |
36460 KB |
Output is correct |
6 |
Correct |
31 ms |
36460 KB |
Output is correct |
7 |
Correct |
51 ms |
38764 KB |
Output is correct |
8 |
Correct |
51 ms |
38764 KB |
Output is correct |
9 |
Correct |
50 ms |
38764 KB |
Output is correct |
10 |
Correct |
317 ms |
51516 KB |
Output is correct |
11 |
Correct |
308 ms |
58220 KB |
Output is correct |
12 |
Correct |
169 ms |
51052 KB |
Output is correct |
13 |
Correct |
2791 ms |
142736 KB |
Output is correct |
14 |
Correct |
2706 ms |
144876 KB |
Output is correct |
15 |
Correct |
2500 ms |
140908 KB |
Output is correct |