#include "quality.h"
#include <bits/stdc++.h>
#define PB push_back
using namespace std;
int Rg, Cg, Hg, Wg;
int sum[3005][3005], q[3005][3005];
//unordered_map<int, bool>a;
int sumar(int i, int j, int dd, int htt){
if(dd<-1||htt<-1)return -1;
return sum[i][j]-((htt>=0 ? sum[i][htt] : 0)+(dd>=0?sum[dd][j]:0))+(dd>=0&&htt>=0 ? sum[dd][htt] : 0);
}
bool check(int x){
//cout<<"x = "<<x<<endl;
/*
for(int i = 0 ; i < Rg ; i++){
sum[i][0]=
}*/
for(int i = 0 ; i < Rg ; i++){
sum[i][0]=(q[i][0] >= x ? 1:-1);
for(int j = 1 ; j < Cg ; j++){
sum[i][j]=sum[i][j-1]+(q[i][j] >= x ? 1:-1);
}
}
/*
for(int i = 0 ; i < Rg ; i ++){
for(int j = 0 ; j < Cg ; j++){
cout<<sum[i][j]<<" ";
}
cout<<endl;
}*/
for(int j = 0 ; j < Cg ; j++){
sum[0][j];
if(sumar(0, j, 0-Hg, 0-Wg)>0)return true;
for(int i = 1 ; i < Rg ; i++){
sum[i][j]+=sum[i-1][j];
if(sumar(i, j, i-Hg, j-Wg)>0)return true;
//cout<<i<<" "<<j<<" = "<<sum[i][j]<<" ";
}
//cout<<endl;
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
Rg=R, Cg=C, Hg=H, Wg=W;
int minimum = INT_MAX;
int li = 1, ls = R*C, pos;
pos=(li+ls)/2;
for(int i = 0 ; i < R ; ++i){
for(int j = 0 ; j < C ; ++j){
q[i][j]=Q[i][j];
}
}
while(li!=ls){
//cout<<li<<" "<<ls<<endl;
pos=(li+ls)/2;
//a[pos]=check(pos);
if(check(pos))ls=pos;
else li=pos+1;
}
/*
for(int i = ls ; i >= li ; i--){
//bool dou = ((a.find(i)==a.end())?check(i):a[i]);
if(check(i))pos=i;
}*/
return li;
}
Compilation message
quality.cpp: In function 'bool check(int)':
quality.cpp:32:11: warning: statement has no effect [-Wunused-value]
32 | sum[0][j];
| ~~~~~~~~^
quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:46:6: warning: unused variable 'minimum' [-Wunused-variable]
46 | int minimum = INT_MAX;
| ^~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
608 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
608 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
608 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
608 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
608 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |