#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
const int mx = 3005;
int csum[mx][mx];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
for(int i = R; i >= 1; i--){
for(int j = C; j >= 1; j--){
Q[i][j] = Q[i-1][j-1];
}
}
int lo = 1;
int hi = R*C;
while(lo < hi){
int mid = (lo+hi)/2;
for(int i = 1; i <= R; i++){
for(int j = 1; j <= C; j++){
if(Q[i][j] < mid){
csum[i][j] = -1;
}
else if(Q[i][j] > mid){
csum[i][j] = 1;
}
else{
csum[i][j] = 0;
}
}
}
// cout << "mid: " << mid << "\n";
// for(int i = 1; i <= R; i++){
// for(int j = 1; j <= C; j++){
// cout << csum[i][j] << " ";
// }
// cout << "\n";
// }
for(int i = 1; i <= R; i++){
for(int j = 1; j <= C; j++){
csum[i][j]+=csum[i-1][j]+csum[i][j-1]-csum[i-1][j-1];
}
}
// cout << "mid: " << mid << "\n";
// for(int i = 1; i <= R; i++){
// for(int j = 1; j <= C; j++){
// cout << csum[i][j] << " ";
// }
// cout << "\n";
// }
bool works = 0;
for(int i = H; i <= R; i++){
for(int j = W; j <= C; j++){
if(csum[i][j]-csum[i-H][j]-csum[i][j-W]+csum[i-H][j-W] <= 0){
//cout << mid << " " << i << " " << j << "\n";
works = 1;
break;
}
}
}
if(works){
hi = mid;
}
else{
lo = mid+1;
}
}
return lo;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
556 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
556 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
4 ms |
1212 KB |
Output is correct |
5 |
Correct |
3 ms |
1228 KB |
Output is correct |
6 |
Correct |
4 ms |
1228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
556 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
4 ms |
1212 KB |
Output is correct |
5 |
Correct |
3 ms |
1228 KB |
Output is correct |
6 |
Correct |
4 ms |
1228 KB |
Output is correct |
7 |
Correct |
25 ms |
3836 KB |
Output is correct |
8 |
Correct |
29 ms |
3912 KB |
Output is correct |
9 |
Correct |
23 ms |
3772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
556 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
4 ms |
1212 KB |
Output is correct |
5 |
Correct |
3 ms |
1228 KB |
Output is correct |
6 |
Correct |
4 ms |
1228 KB |
Output is correct |
7 |
Correct |
25 ms |
3836 KB |
Output is correct |
8 |
Correct |
29 ms |
3912 KB |
Output is correct |
9 |
Correct |
23 ms |
3772 KB |
Output is correct |
10 |
Correct |
323 ms |
22876 KB |
Output is correct |
11 |
Correct |
309 ms |
22872 KB |
Output is correct |
12 |
Correct |
156 ms |
15464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
556 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
4 ms |
1212 KB |
Output is correct |
5 |
Correct |
3 ms |
1228 KB |
Output is correct |
6 |
Correct |
4 ms |
1228 KB |
Output is correct |
7 |
Correct |
25 ms |
3836 KB |
Output is correct |
8 |
Correct |
29 ms |
3912 KB |
Output is correct |
9 |
Correct |
23 ms |
3772 KB |
Output is correct |
10 |
Correct |
323 ms |
22876 KB |
Output is correct |
11 |
Correct |
309 ms |
22872 KB |
Output is correct |
12 |
Correct |
156 ms |
15464 KB |
Output is correct |
13 |
Correct |
3106 ms |
89572 KB |
Output is correct |
14 |
Correct |
3021 ms |
89676 KB |
Output is correct |
15 |
Correct |
2775 ms |
87216 KB |
Output is correct |