#include<bits/stdc++.h>
#include "quality.h"
#define ll long long
#define pb push_back
using namespace std;
int h , w , r , c , grid[3001][3001] , pref[3001][3001];
void reset(){
for(int i = 0 ; i <= r ; i++){
for(int j = 0 ; j <= c ; j++){
pref[i][j] = 0;
}
}
}
bool inside(int x , int y){
return 0 < x && x <= r && 0 < y && y <= c;
}
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 = 1 ; i <= r ; i++){
for(int j = 1 ; j <= c ; j++){
grid[i][j] = Q[i - 1][j - 1];
}
}
int lef = 0 , rig = r * c , ans = 0;
while(lef <= rig){
int mid = (lef + rig) / 2;
reset();
for(int i = 1 ; i <= r ; i++){
for(int j = 1 ; j <= c ; j++){
pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + (grid[i][j] <= mid);
}
}
bool bs = false;
for(int i = 1 ; i <= r ; i++){
for(int j = 1 ; j <= c ; j++){
int x = i , y = j , x0 = x + h - 1 , y0 = y + w - 1;
if(inside(x0 , y0)){
int tt = pref[x0][y0] - pref[x - 1][y0] - pref[x0][y - 1] + pref[x - 1][y - 1];
//cout << x << " " << y << " " << x0 << " " << y0 << " " << pref[x0][y0] << " " << pref[x][y0] << " " << pref[x0][y] << " " << pref[x][y] << endl;
if(tt > (h * w) / 2) bs = true;
}
}
}
if(bs){
ans = mid;
rig = mid - 1;
}
else{
lef = mid + 1;
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
688 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
688 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
3 ms |
1620 KB |
Output is correct |
5 |
Correct |
3 ms |
1584 KB |
Output is correct |
6 |
Correct |
3 ms |
1620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
688 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
3 ms |
1620 KB |
Output is correct |
5 |
Correct |
3 ms |
1584 KB |
Output is correct |
6 |
Correct |
3 ms |
1620 KB |
Output is correct |
7 |
Correct |
15 ms |
5436 KB |
Output is correct |
8 |
Correct |
16 ms |
5460 KB |
Output is correct |
9 |
Correct |
13 ms |
5332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
688 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
3 ms |
1620 KB |
Output is correct |
5 |
Correct |
3 ms |
1584 KB |
Output is correct |
6 |
Correct |
3 ms |
1620 KB |
Output is correct |
7 |
Correct |
15 ms |
5436 KB |
Output is correct |
8 |
Correct |
16 ms |
5460 KB |
Output is correct |
9 |
Correct |
13 ms |
5332 KB |
Output is correct |
10 |
Correct |
168 ms |
30692 KB |
Output is correct |
11 |
Correct |
172 ms |
30772 KB |
Output is correct |
12 |
Correct |
84 ms |
21452 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
688 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
3 ms |
1620 KB |
Output is correct |
5 |
Correct |
3 ms |
1584 KB |
Output is correct |
6 |
Correct |
3 ms |
1620 KB |
Output is correct |
7 |
Correct |
15 ms |
5436 KB |
Output is correct |
8 |
Correct |
16 ms |
5460 KB |
Output is correct |
9 |
Correct |
13 ms |
5332 KB |
Output is correct |
10 |
Correct |
168 ms |
30692 KB |
Output is correct |
11 |
Correct |
172 ms |
30772 KB |
Output is correct |
12 |
Correct |
84 ms |
21452 KB |
Output is correct |
13 |
Correct |
1665 ms |
175236 KB |
Output is correct |
14 |
Correct |
1621 ms |
175236 KB |
Output is correct |
15 |
Correct |
1491 ms |
168216 KB |
Output is correct |