Türkçe

Verilen ızgaranın üzerindeki bir alandaki ekilebilir alanı bulmak için "Submatrix Sum Query" yöntemini kullanabiliriz.

İlk önce her 1x1 alan için o alanda ve sol üstündeki alanlarda ekilebilecek toprakların toplamını \(O(\mathbf{N\cdot M})\) sürede buluruz. Bunu yapmak için sol üstten başlayıp sırasıyla tüm 1x1 alanlar için üstü ve solu için bulduğumuz değerlerle şu andaki alanın değerini toplarız. Sol üstteki alanı iki kere kattığımız için de bu alanı çıkarırız.

\(grid[i][j] = grid[i][j-1] + grid[i-1][j] - grid[i-1][j-1]\)

Bu işlemlerin sonucunda herhangi bir alandaki ekilebilir toprak sayısını alttaki formül ile \(O(1)\) sürede bulabiliriz. (Alttaki formülde \(\mathbf{Y \times X}\) büyüklüğünde ve sol üst köşesi \(i, j\)'de olan bir dikdörtgenin alanı bulunuyor.)

\(area[i][j] = grid[i][j] - grid[i-\mathbf{X}][j] - grid[i][j-\mathbf{Y}] - grid[i-\mathbf{X}][j-\mathbf{Y}]\)

Verilen \(\mathbf{Y \times X}\) alan boyutunu sağlayacak tüm alanlardaki ekilebilecek toprakların sayısını \(O(\mathbf{N\cdot M})\)'de bulabiliriz. Bu alanların maksimumu da aradığımız cevap.

English

We can use "Submatrix Sum Query" method to find the cultivable area in an area above the given grid.

First, for each 1x1 area, we find the total of the lands that can be cultivated in that area and the areas above left in \(O(\mathbf{N\cdot M})\) time. To accomplish this, we start from the top left and add the values ​​for the top and left for all 1x1 areas, respectively, and the value of the current area. Since the upper left area is added twice, this area is subtracted.

\(grid[i][j] = grid[i][j-1] + grid[i-1][j] - grid[i-1][j-1]\)

As a result of these processes, we can find the number of arable land in any area in \(O(1)\) time with the formula below. (The formula below has the area of ​​a rectangle of \(\mathbf{Y \times X}\) with the upper-left corner at \(i, j\).)

\(area[i][j] = grid[i][j] - grid[i-\mathbf{X}][j] - grid[i][j-\mathbf{Y}] - grid[i-\ mathbf{X}][j-\mathbf{Y}]\)

In \(O(\mathbf{N\cdot M})\) we can find the number of cultivable lands in all areas that will provide the given \(\mathbf{Y \times X}\) field size. The maximum of these areas is the answer we are looking for.

#include <bits/stdc++.h>

using namespace std;

const int siz = 1005;

int n, m, nn, mm, grid[siz][siz];
string inp[siz];

int main(){
    cin>>n>>m>>nn>>mm;
    for(int i=1;i<=n;i++) cin>>inp[i];

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            grid[i][j] = grid[i][j-1] + grid[i-1][j] - grid[i-1][j-1];   
            if(inp[i][j-1]=='.') grid[i][j]++;
        }    
    }

    int mSum = 0;
    for(int i=nn;i<=n;i++){
        for(int j=mm;j<=m;j++){
            int nSum = grid[i][j];
            nSum -= grid[i-nn][j];
            nSum -= grid[i][j-mm];
            nSum += grid[i-nn][j-mm];
            mSum = mSum < nSum ? nSum : mSum;  
        }
    }
    cout<<mSum;
}