#include "quality.h" #include<bits/stdc++.h> using namespace std; const int lim = 3e3 + 1; int f[lim][lim]; int rectangle(int n, int m, int H, int W, int Q[3001][3001]){ memset(f, 0, sizeof(f)); int low = 1, high = n * m, ans; while(low <= high){ int mid = (low + high) >> 1; for(int i = 1; i <= n; i++){ for(int j = 1, s = 0; j <= m; j++){ f[i][j] = (s += (Q[i - 1][j - 1] > mid ? -1 : 1)) + f[i - 1][j]; } } bool flag = false; for(int i = H; i <= n; i++){ for(int j = W; j <= m; j++){ if(f[i][j] - f[i][j - W] - f[i - H][j] + f[i - H][j - W] > 0){ flag = true; i = n; break; } } } if(flag){ high = (ans = mid) - 1; } else{ low = mid + 1; } } return ans; }