AtCoder Beginner Contest 203 Pond(二分+二维前缀和)

3 2
1 7 0
5 8 11
10 4 2

3 3
1 2 3
4 5 6
7 8 9

typedef int itn;
int a[809][809];
int s[809][809];
int main() {
  int n = read,k =  read;
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      a[i][j] = read;
    }
  }
  int p = k * k / 2 + 1;
  int l = -1,r = 0x3f3f3f3f;
  bool flag = 0;
  while(l + 1 < r) {
    int mid = l+r >> 1;
    for(int i=0; i<n; i++) {
      for(int j=0; j<n; j++) {
        s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j];
        if(a[i][j] > mid) s[i+1][j+1] ++;
      }
    }
    flag = 0;
    for(int i=0; i<n-k+1; i++) {
      for(int j=0; j<n-k+1; j++) {
        int val = s[i+k][j+k] + s[i][j] - s[i][j+k] - s[i+k][j];
        if(val < p) {
          flag = 1;
          break;
        }
      }
      if(flag) break;
    }
    if(flag) r = mid;
    else l = mid;
  }
  cout << l + 1 <<endl;
  return 0;
}