The solution here hinges on the fact that we don't care about most of the 3x3 subrectangles.

Let's pick any uncolored cell. You can see that any 3x3 subrectangle that would contain that cell would be fully contained within the 5x5 subrectangle in which that cell is the middle. This means that if no cell in the 5x5 subrectangle where the target cell is the middle is colored, then we don't care about that point.

At most $$$9$$$ subrectangles will go through a single point, so there are at most $$$9N$$$ subrectangles we have to worry about. For each point, generate the subrectangles that contain that point (you can iterate through the position in the subrectangle that our target point is in, also be careful about edges). Also, remove duplicates in some way. This process is probably $$$O(nlogn)$$$ because of sorting or something.

Now, for each subrectangle, we will count how many colored cells are in it. We can do this by keeping each point in some ordered list (perhaps a C++ set) and checking each of the 9 points in each rectangle. This is our answer.

The total number of rectangles is $$$(H - 2) * (W - 2)$$$, and if we haven't looked at a rectangle, it has 0 points inside it, so you can just subtract the number of rectangles we've looked at and add that to $$$count(0)$$$.

I got bored and wanted to prove that the constant wouldn't be too bad, so here's a submission with time = 396 ms.