White Lines
Contest: Codeforces Round 578 (Div. 2)
Difficulty rating: 1900
Tags: brute force, data structures, dp, implementation, two pointers

Gildong has bought a famous painting software cfpaint. The working screen of cfpaint is square-shaped consisting of $$$n$$$ rows and $$$n$$$ columns of square cells. The rows are numbered from $$$1$$$ to $$$n$$$, from top to bottom, and the columns are numbered from $$$1$$$ to $$$n$$$, from left to right. The position of a cell at row $$$r$$$ and column $$$c$$$ is represented as $$$(r, c)$$$. There are only two colors for the cells in cfpaint — black and white.

There is a tool named eraser in cfpaint. The eraser has an integer size $$$k$$$ ($$$1 \le k \le n$$$). To use the eraser, Gildong needs to click on a cell $$$(i, j)$$$ where $$$1 \le i, j \le n - k + 1$$$. When a cell $$$(i, j)$$$ is clicked, all of the cells $$$(i', j')$$$ where $$$i \le i' \le i + k - 1$$$ and $$$j \le j' \le j + k - 1$$$ become white. In other words, a square with side equal to $$$k$$$ cells and top left corner at $$$(i, j)$$$ is colored white.

A white line is a row or a column without any black cells.

Gildong has worked with cfpaint for some time, so some of the cells (possibly zero or all) are currently black. He wants to know the maximum number of white lines after using the eraser exactly once. Help Gildong find the answer to his question.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2000$$$) — the number of rows and columns, and the size of the eraser.

The next $$$n$$$ lines contain $$$n$$$ characters each without spaces. The $$$j$$$-th character in the $$$i$$$-th line represents the cell at $$$(i,j)$$$. Each character is given as either 'B' representing a black cell, or 'W' representing a white cell.

Output format:
Print one integer: the maximum number of white lines after using the eraser exactly once.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
In the first example, Gildong can click the cell $$$(2, 2)$$$, then the working screen becomes:

Then there are four white lines — the $$$2$$$-nd and $$$3$$$-rd row, and the $$$2$$$-nd and $$$3$$$-rd column.

In the second example, clicking the cell $$$(2, 3)$$$ makes the $$$2$$$-nd row a white line.

In the third example, both the $$$2$$$-nd column and $$$5$$$-th row become white lines by clicking the cell $$$(3, 2)$$$.

Example input:
4 2
BWWW
WBBW
WBBW
WWWB

Example output:
4

Example input:
3 1
BWB
WWB
BWB

Example output:
2

Editorial:
Let's consider a single row that contains at least one black cell. If the first appearance of a black cell is at the $$$l$$$-th column and the last appearance of a black cell is at the $$$r$$$-th column, we can determine whether it becomes a white line when a certain cell $$$(i, j)$$$ is clicked in $$$O(1)$$$, after some preprocessing. It becomes a white line if and only if a cell $$$(i,j)$$$ is clicked where the row is at $$$[i,i+k-1]$$$ and $$$j \le l \le r \le j+k-1$$$. We just need to compute $$$l$$$ and $$$r$$$ in advance.
Now let's consider all $$$n$$$ rows (not columns). First, count all rows that are already white lines before clicking. Then we count the number of white rows when the cell $$$(1,1)$$$ is clicked, by applying the above method to all rows from $$$1$$$ to $$$k$$$. Ignore the already-white rows that we counted before. So far we obtained the number of white rows when the cell $$$(1,1)$$$ is clicked. From now, we slide the window. Add the $$$k+1$$$-st row and remove the $$$1$$$-st row by applying the same method to them, and we obtain the number of white rows when the cell $$$(2,1)$$$ is clicked. We can repeat this until we calculate all $$$n-k+1$$$ cases for clicking the cells at the $$$1$$$-st column. Then we repeat the whole process for all $$$n-k+1$$$ columns.
The same process can be done for counting white columns, too. Now we know the number of white rows and white columns when each cell is clicked, so we can find the maximum value among their sums.
Time complexity: $$$O(n^2)$$$