#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
int smaller[R+1][C+1] , bigger[R+1][C+1] , arr[R+1][C+1];
//make grid 1-indexed
memset(smaller , 0 , sizeof(smaller)) ;
memset(bigger , 0 , sizeof(bigger)) ;
for(int i = 1 ; i <= R ; ++i)
{
for(int j = 1 ; j <= C ; ++j)
arr[i][j] = Q[i-1][j-1] ;
}
int l = 1 , r = R*C , ans = R*C ;
while(l <= r)
{
int mid = (l + r) / 2 ;
for(int i = 1 ; i <= R ; ++i)
{
int s = 0 , b = 0 ;
for(int j = 1 ; j <= C ; ++j)
{
smaller[i][j] = s + smaller[i-1][j];
if(arr[i][j] < mid)
smaller[i][j]++ , ++s;
bigger[i][j] = b + bigger[i-1][j] ;
if(arr[i][j] > mid)
bigger[i][j]++ , ++b;
}
}
bool t = false ;
for(int i = 1 ; i <= R-H+1 ; ++i)
{
for(int j = 1 ; j <= C-W+1 ; ++j)
{
int s = smaller[i+H-1][j+W-1] - smaller[i+H-1][j-1] - smaller[i-1][j+W-1] + smaller[i-1][j-1] ;
int b = bigger[i+H-1][j+W-1] - bigger[i+H-1][j-1] - bigger[i-1][j+W-1] + bigger[i-1][j-1] ;
if(s >= b)
t = true ;
int n = R*C ;
if(s == b && s <= n/2 && b <= n/2)
ans = min(ans , mid) ;
}
}
if(t == true)
r = mid-1 ;
else
l = mid+1 ;
}
return ans ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
408 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 |
408 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 |
836 KB |
Output is correct |
5 |
Correct |
3 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 |
408 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 |
836 KB |
Output is correct |
5 |
Correct |
3 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
20 ms |
3396 KB |
Output is correct |
8 |
Correct |
20 ms |
3412 KB |
Output is correct |
9 |
Correct |
17 ms |
3136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
408 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 |
836 KB |
Output is correct |
5 |
Correct |
3 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
20 ms |
3396 KB |
Output is correct |
8 |
Correct |
20 ms |
3412 KB |
Output is correct |
9 |
Correct |
17 ms |
3136 KB |
Output is correct |
10 |
Correct |
246 ms |
26712 KB |
Output is correct |
11 |
Correct |
242 ms |
26812 KB |
Output is correct |
12 |
Correct |
117 ms |
15532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
408 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 |
836 KB |
Output is correct |
5 |
Correct |
3 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
20 ms |
3396 KB |
Output is correct |
8 |
Correct |
20 ms |
3412 KB |
Output is correct |
9 |
Correct |
17 ms |
3136 KB |
Output is correct |
10 |
Correct |
246 ms |
26712 KB |
Output is correct |
11 |
Correct |
242 ms |
26812 KB |
Output is correct |
12 |
Correct |
117 ms |
15532 KB |
Output is correct |
13 |
Correct |
2331 ms |
210568 KB |
Output is correct |
14 |
Correct |
2289 ms |
210692 KB |
Output is correct |
15 |
Correct |
2121 ms |
192760 KB |
Output is correct |