#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
using idata = vector<int>;
using igrid = vector<idata>;
igrid VC;
bool check (int R, int C, int H, int W, igrid &V, int M) {
int count = (H * W + 1) >> 1;
for (int i = 0; i <= R; i ++)
VC[i][0] = 0;
for (int i = 0; i <= C; i ++)
VC[0][i] = 0;
for (int i = 1; i <= R; i ++) {
for (int j = 1; j <= C; j ++) {
VC[i][j] = VC[i - 1][j]
+ VC[i][j - 1]
- VC[i - 1][j - 1]
+ (V[i - 1][j - 1] <= M ? 1 : 0);
}
}
for (int i = 0; i + H <= R; i ++) {
for (int j = 0; j + W <= C; j ++) {
int lc = VC[i][j] + VC[i + H][j + W]
- (VC[i + H][j] + VC[i][j + W]);
if (lc >= count) return true;
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
VC.resize(R + 1, idata(C + 1));
igrid V(R, idata(C));
for (int i = 0; i < R; i ++)
for (int j = 0; j < C; j ++)
V[i][j] = Q[i][j];
int a = 0;
int b = R * C;
while (b - a > 1) {
int c = (a + b) >> 1;
if (check(R, C, H, W, V, c)) b = c;
else a = c;
}
return b;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
976 KB |
Output is correct |
5 |
Correct |
2 ms |
980 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
976 KB |
Output is correct |
5 |
Correct |
2 ms |
980 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
13 ms |
3008 KB |
Output is correct |
8 |
Correct |
15 ms |
3008 KB |
Output is correct |
9 |
Correct |
11 ms |
2900 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
976 KB |
Output is correct |
5 |
Correct |
2 ms |
980 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
13 ms |
3008 KB |
Output is correct |
8 |
Correct |
15 ms |
3008 KB |
Output is correct |
9 |
Correct |
11 ms |
2900 KB |
Output is correct |
10 |
Correct |
153 ms |
22852 KB |
Output is correct |
11 |
Correct |
148 ms |
22844 KB |
Output is correct |
12 |
Correct |
75 ms |
13516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
976 KB |
Output is correct |
5 |
Correct |
2 ms |
980 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
13 ms |
3008 KB |
Output is correct |
8 |
Correct |
15 ms |
3008 KB |
Output is correct |
9 |
Correct |
11 ms |
2900 KB |
Output is correct |
10 |
Correct |
153 ms |
22852 KB |
Output is correct |
11 |
Correct |
148 ms |
22844 KB |
Output is correct |
12 |
Correct |
75 ms |
13516 KB |
Output is correct |
13 |
Correct |
1497 ms |
175444 KB |
Output is correct |
14 |
Correct |
1425 ms |
175488 KB |
Output is correct |
15 |
Correct |
1325 ms |
161252 KB |
Output is correct |