#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int tab[R][C];
vector<int> V;
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
V.push_back(Q[i][j]);
}
}
sort(V.begin(), V.end());
int l=0, r=V.size()-1;
while(l<r){
bool b=0;
int m=(l+r+1)>>1;
int k=V[m];
//cerr<<V[m]<<"\n";
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
tab[i][j]=(Q[i][j]<k);
//cout<<tab[i][j]<<" ";
}
//cout<<"\n";
}
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
if(i)tab[i][j]+=tab[i-1][j];
if(j)tab[i][j]+=tab[i][j-1];
if(i && j)tab[i][j]-=tab[i-1][j-1];
//cout<<tab[i][j]<<" ";
if(i>=H-1 && j>=W-1){
int t=tab[i][j];
if(i>=H)t-=tab[i-H][j];
if(j>=W)t-=tab[i][j-W];
if(i>=H && j>=W)t+=tab[i-H][j-W];
if(t>H*W/2)b=1;
}
}
//cout<<"\n";
}
//cerr<<b<<"\n";
if(b)r=m-1;
else l=m;
}
return V[l];
}
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
4 ms |
844 KB |
Output is correct |
5 |
Correct |
3 ms |
844 KB |
Output is correct |
6 |
Correct |
4 ms |
928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
4 ms |
844 KB |
Output is correct |
5 |
Correct |
3 ms |
844 KB |
Output is correct |
6 |
Correct |
4 ms |
928 KB |
Output is correct |
7 |
Correct |
27 ms |
3380 KB |
Output is correct |
8 |
Correct |
26 ms |
3272 KB |
Output is correct |
9 |
Correct |
25 ms |
3144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
4 ms |
844 KB |
Output is correct |
5 |
Correct |
3 ms |
844 KB |
Output is correct |
6 |
Correct |
4 ms |
928 KB |
Output is correct |
7 |
Correct |
27 ms |
3380 KB |
Output is correct |
8 |
Correct |
26 ms |
3272 KB |
Output is correct |
9 |
Correct |
25 ms |
3144 KB |
Output is correct |
10 |
Correct |
329 ms |
23216 KB |
Output is correct |
11 |
Correct |
325 ms |
23092 KB |
Output is correct |
12 |
Correct |
157 ms |
13616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
4 ms |
844 KB |
Output is correct |
5 |
Correct |
3 ms |
844 KB |
Output is correct |
6 |
Correct |
4 ms |
928 KB |
Output is correct |
7 |
Correct |
27 ms |
3380 KB |
Output is correct |
8 |
Correct |
26 ms |
3272 KB |
Output is correct |
9 |
Correct |
25 ms |
3144 KB |
Output is correct |
10 |
Correct |
329 ms |
23216 KB |
Output is correct |
11 |
Correct |
325 ms |
23092 KB |
Output is correct |
12 |
Correct |
157 ms |
13616 KB |
Output is correct |
13 |
Correct |
3091 ms |
162704 KB |
Output is correct |
14 |
Correct |
3027 ms |
166500 KB |
Output is correct |
15 |
Correct |
2802 ms |
116864 KB |
Output is correct |