#include "quality.h"
#include<vector>
#include<iostream>
using namespace std;
bool solve(int R, int C, int H, int W, int Q[3001][3001],int mid)
{
vector<vector<int> > grid(R,vector<int>(C));
for(int i=0;i<R;i++)
{
for(int j=0;j<C;j++)
{
if(Q[i][j]<=mid) grid[i][j]=-1;
else grid[i][j]=1;
}
}
for(int j=1;j<C;j++)
{
grid[0][j]+=grid[0][j-1];
}
for(int i=1;i<R;i++)
{
grid[i][0]+=grid[i-1][0];
}
for(int i=1;i<R;i++)
{
for(int j=1;j<C;j++)
{
grid[i][j]+=grid[i-1][j]+grid[i][j-1]-grid[i-1][j-1];
}
}
for(int i=H-1;i<R;i++)
{
for(int j=W-1;j<C;j++)
{
int chk=grid[i][j];
if(i>=H) chk-=grid[i-H][j];
if(j>=W) chk-=grid[i][j-W];
if(i>=H && j>=W) chk+=grid[i-H][j-W];
if(chk<0) return true;
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int l=1,r=R*C;
int mid,ans;
while(l<r)
{
mid=l+(r-l)/2;
bool possible=solve(R,C,H,W,Q,mid);
if(possible)
{
ans=mid;
r=mid-1;
}else
{
l=mid+1;
}
}
if(l==r && solve(R,C,H,W,Q,l)) ans=min(l,ans);
return ans;
}
Compilation message
quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:48:13: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
48 | int mid,ans;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
3 ms |
716 KB |
Output is correct |
5 |
Correct |
3 ms |
716 KB |
Output is correct |
6 |
Correct |
3 ms |
716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
3 ms |
716 KB |
Output is correct |
5 |
Correct |
3 ms |
716 KB |
Output is correct |
6 |
Correct |
3 ms |
716 KB |
Output is correct |
7 |
Correct |
28 ms |
2212 KB |
Output is correct |
8 |
Correct |
31 ms |
2736 KB |
Output is correct |
9 |
Correct |
26 ms |
2624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
3 ms |
716 KB |
Output is correct |
5 |
Correct |
3 ms |
716 KB |
Output is correct |
6 |
Correct |
3 ms |
716 KB |
Output is correct |
7 |
Correct |
28 ms |
2212 KB |
Output is correct |
8 |
Correct |
31 ms |
2736 KB |
Output is correct |
9 |
Correct |
26 ms |
2624 KB |
Output is correct |
10 |
Correct |
364 ms |
18904 KB |
Output is correct |
11 |
Correct |
356 ms |
19008 KB |
Output is correct |
12 |
Correct |
218 ms |
11556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
3 ms |
716 KB |
Output is correct |
5 |
Correct |
3 ms |
716 KB |
Output is correct |
6 |
Correct |
3 ms |
716 KB |
Output is correct |
7 |
Correct |
28 ms |
2212 KB |
Output is correct |
8 |
Correct |
31 ms |
2736 KB |
Output is correct |
9 |
Correct |
26 ms |
2624 KB |
Output is correct |
10 |
Correct |
364 ms |
18904 KB |
Output is correct |
11 |
Correct |
356 ms |
19008 KB |
Output is correct |
12 |
Correct |
218 ms |
11556 KB |
Output is correct |
13 |
Correct |
3449 ms |
140208 KB |
Output is correct |
14 |
Correct |
3367 ms |
140428 KB |
Output is correct |
15 |
Correct |
3084 ms |
129752 KB |
Output is correct |