DMOPC '20 Contest 5 P4 - Slacking Off

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

After finishing one task at work, Bob is getting bored. So he decides to count some patterns in the N-pixel-high by M-pixel-wide computer screen his employer gave him. Each pixel is either yellow (lit) or black (unlit).

Bob thinks a rectangle of pixels, with both dimensions at least 2, is ugly if its first and last rows are identical and its first and last columns are identical. (Note: this definition is the same as the one in Problem 5.) For example, the following rectangles are ugly:

Please help Bob count the number of ugly sub-rectangles in the N \times M screen!


2 \le N, M

4 \le N \times M \le 200\,000

Subtask 1 [10%]

4 \le N \times M \le 500

Subtask 2 [20%]

4 \le N \times M \le 8000

Subtask 3 [70%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, N and M.
The next N lines each contain a string of M characters—Y for yellow and B for black—representing the colours of the pixels on the screen.

Output Specification

Output one integer, the number of ugly sub-rectangles.

Sample Input

3 3

Sample Output



There are no comments at the moment.