#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int r, c, h, w, q[3001][3001];
int add[301][301];
array<int, 2> pos [90001];
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 < 301; i++)
{
for (int j = 0; j < 301; j++) q[i][j] = Q[i][j];
}
return bs();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2028 KB |
Output is correct |
2 |
Correct |
3 ms |
2028 KB |
Output is correct |
3 |
Correct |
2 ms |
2028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2028 KB |
Output is correct |
2 |
Correct |
3 ms |
2028 KB |
Output is correct |
3 |
Correct |
2 ms |
2028 KB |
Output is correct |
4 |
Correct |
4 ms |
2592 KB |
Output is correct |
5 |
Correct |
4 ms |
2540 KB |
Output is correct |
6 |
Correct |
4 ms |
2560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2028 KB |
Output is correct |
2 |
Correct |
3 ms |
2028 KB |
Output is correct |
3 |
Correct |
2 ms |
2028 KB |
Output is correct |
4 |
Correct |
4 ms |
2592 KB |
Output is correct |
5 |
Correct |
4 ms |
2540 KB |
Output is correct |
6 |
Correct |
4 ms |
2560 KB |
Output is correct |
7 |
Correct |
24 ms |
3948 KB |
Output is correct |
8 |
Correct |
26 ms |
4476 KB |
Output is correct |
9 |
Correct |
21 ms |
4204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2028 KB |
Output is correct |
2 |
Correct |
3 ms |
2028 KB |
Output is correct |
3 |
Correct |
2 ms |
2028 KB |
Output is correct |
4 |
Correct |
4 ms |
2592 KB |
Output is correct |
5 |
Correct |
4 ms |
2540 KB |
Output is correct |
6 |
Correct |
4 ms |
2560 KB |
Output is correct |
7 |
Correct |
24 ms |
3948 KB |
Output is correct |
8 |
Correct |
26 ms |
4476 KB |
Output is correct |
9 |
Correct |
21 ms |
4204 KB |
Output is correct |
10 |
Incorrect |
201 ms |
15232 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2028 KB |
Output is correct |
2 |
Correct |
3 ms |
2028 KB |
Output is correct |
3 |
Correct |
2 ms |
2028 KB |
Output is correct |
4 |
Correct |
4 ms |
2592 KB |
Output is correct |
5 |
Correct |
4 ms |
2540 KB |
Output is correct |
6 |
Correct |
4 ms |
2560 KB |
Output is correct |
7 |
Correct |
24 ms |
3948 KB |
Output is correct |
8 |
Correct |
26 ms |
4476 KB |
Output is correct |
9 |
Correct |
21 ms |
4204 KB |
Output is correct |
10 |
Incorrect |
201 ms |
15232 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |