#include "quality.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+50;
const int SQRT = 610;
const int MAXA = 50;
const int MOD = 998244353;
const int LOG = 21;
const int INF = 1e16+100;
const int INF2 = 1e18;
const ld EPS = 1e-12;
int n, m, h, w;
int a[3010][3010], pr[3010][3010];
int cek(int x){
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
pr[i][j] = pr[i-1][j]+pr[i][j-1]-pr[i-1][j-1];
pr[i][j] += (a[i][j] <= x);
}
}
for(int i=h; i<=n; i++){
for(int j=w; j<=m; j++){
if(pr[i][j]-pr[i-h][j]-pr[i][j-w]+pr[i-h][j-w]
>= h*w/2+1) return 1;
}
}
return 0;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
n = R, m = C, h = H, w = W;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
a[i][j] = Q[i-1][j-1];
}
}
int l=1, r=n*m, mid=0, cnt=-1;
while(l<=r){
mid = md;
if(cek(mid)) cnt = mid, r = mid-1;
else l = mid+1;
}
// for(int i=1; i<=n*m; i++){
// cout << i << ' ' << cek(i) << " cek\n";
// }
return cnt;
}
Compilation message (stderr)
quality.cpp:21:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.00000000000001e+16' to '2147483647' [-Woverflow]
21 | const int INF = 1e16+100;
| ~~~~^~~~
quality.cpp:22:18: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
22 | const int INF2 = 1e18;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |