#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
vector<vector<int>> a(R + 1, vector<int>(C + 1));
for (int i = 1; i <= R; i++){
for (int j = 1; j <= C; j++){
a[i][j] = Q[i - 1][j - 1];
}
}
int l = 1, r = R * C;
vector<vector<int>> p(R + 1, vector<int>(C + 1, 0));
while (l != r){
int m = (l + r)/2;
bool good = false;
for (int i = 1; i <= R; i++){
for (int j = 1; j <= C; j++){
p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
if (a[i][j] <= m) {
p[i][j]++;
// cout << i << " " << j << "\n";
}
}
}
// cout << m << "\n";
// for (int i = 1; i <= R; i++){
// for (int j = 1; j <= C; j++){
// cout << p[i][j] << " \n"[j == C];
// }
// }
for (int i = 1; i <= R; i++){
for (int j = 1; j <= C; j++){
int x = i + H - 1;
int y = j + W - 1;
if (x > R || y > C) continue;
int val = p[x][y] + p[i - 1][j - 1] - p[x][j - 1] - p[i - 1][y];
if (val > (H * W) / 2) good = true;
}
}
if (good) r = m;
else l = m + 1;
}
return l;
}
// int main(){
// int r, c, h, w; int Q[3001][3001];
// cin >> r >> c >> h >> w;
// for (int i = 1; i <= r; i++){
// for (int j = 1; j <= c; j++){
// cin >> Q[i - 1][j - 1];
// }
// }
// cout << rectangle(r, c, h, w, Q);
// return 0;
// }
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
3 ms |
852 KB |
Output is correct |
5 |
Correct |
2 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
3 ms |
852 KB |
Output is correct |
5 |
Correct |
2 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
19 ms |
3036 KB |
Output is correct |
8 |
Correct |
20 ms |
3028 KB |
Output is correct |
9 |
Correct |
14 ms |
2948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
3 ms |
852 KB |
Output is correct |
5 |
Correct |
2 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
19 ms |
3036 KB |
Output is correct |
8 |
Correct |
20 ms |
3028 KB |
Output is correct |
9 |
Correct |
14 ms |
2948 KB |
Output is correct |
10 |
Correct |
197 ms |
22844 KB |
Output is correct |
11 |
Correct |
200 ms |
22804 KB |
Output is correct |
12 |
Correct |
94 ms |
13428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
3 ms |
852 KB |
Output is correct |
5 |
Correct |
2 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
19 ms |
3036 KB |
Output is correct |
8 |
Correct |
20 ms |
3028 KB |
Output is correct |
9 |
Correct |
14 ms |
2948 KB |
Output is correct |
10 |
Correct |
197 ms |
22844 KB |
Output is correct |
11 |
Correct |
200 ms |
22804 KB |
Output is correct |
12 |
Correct |
94 ms |
13428 KB |
Output is correct |
13 |
Correct |
1950 ms |
155888 KB |
Output is correct |
14 |
Correct |
1909 ms |
155764 KB |
Output is correct |
15 |
Correct |
1759 ms |
143476 KB |
Output is correct |