#include "quality.h" #include <bits/stdc++.h> using namespace std; const int N = 3e3; int pre[N+5][N+5]; int get(int u, int v, int x, int y) { return pre[x][y]-pre[u-1][y]-pre[x][v-1]+pre[u-1][v-1]; } int rectangle(int n, int m, int h, int w, int a[3001][3001]) { int l = 1, r = n*m, ans = -1; while (l <= r) { int mid = (l+r)/2; for (int x = 1; x <= n; x++) { for (int y = 1; y <= m; y++) { pre[x][y] = pre[x-1][y]+pre[x][y-1]-pre[x-1][y-1]+(a[x-1][y-1] <= mid ? 1 : -1); } } bool check = 0; for (int x = h; x <= n && !check; x++) { for (int y = w; y <= m && !check; y++) { if (get(x-h+1, y-w+1, x, y) >= 0) check = 1; } } if (check) { r = (ans = mid)-1; } else { l = mid+1; } } return ans; }