#include "quality.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define endl '\n' #define fi first #define se second #define pb push_back #define FOR(i,l,r) for(ll i=(l),_r=(r);i<=_r;i++) #define FORNG(i,r,l) for(ll i=(r),_l=(l);i>=_l;i--) #define MASK(i) (1LL<<(i)) #define BIT(x,i) (((x)>>(i))&1LL) #define all(v) (v).begin(),(v).end() #define sz(v) ((ll)(v).size()) const ll MOD = 1e9+7, N = 3001; ll n,m,w,h,a[N][N],ans; ll b[N][N]; bool check(ll x){ FOR(i,1,n)FOR(j,1,m){ b[i][j] = b[i][j-1] + b[i-1][j] - b[i-1][j-1] + (a[i][j]>=x?+1:-1); if(i>=w && j >= h){ ll s = b[i][j] - b[i][j-h] - b[i-w][j] + b[i-w][j-h]; if(s>=0)return 1; } } return 0; } ll solve(){ ll l = 1, r = n*m; while(l <= r){ ll mid = (l + r) >> 1; if(check(mid)){ l = mid + 1; ans = mid; }else r = mid - 1; } return ans; } int rectangle(int R, int C, int H, int W, int Q[3001][3001]) { n = R, m = C, w = H, h = W; FOR(i,1,n)FOR(j,1,m)a[i][j] = Q[i - 1][j - 1]; return solve(); }