Problem link: 128C - Games with Rectangle
Official Editorial: Russian only

I've got idea that is different from the official one, plus:

• with worse time complexity
• with worse memory requirements
• and it seems to be incorrect one

But the problem is, I can't find what I am missing :(
Here is my code (unfortunately, it is full of trash, and I am too lazy to remove them). So I am asking you to help.

Brief description

Initially there is a grid and a rectangle already drawn on it of size n × m.You need to draw k more rectangles and each rectangle should be drawn inside the previously drawn rectangle. Rectangles' sides should be one the grid lines and they should not touch each other. The problem is in how many ways you can do it (or, how many different pictures can you draw in total).

My solution

Let's assume that there is a grid of size w × h. Let g(w, h, k) be number of different pictures you can obtain by drawing k rectangles one inside another (plus, they should be drawn on the grid lines and their borders should not touch each other). It is clear that answer for the whole problem will be g(n - 1, m - 1, k). Now we need to know how to calculate g:

g[w][h][k] = 2*g[w][h-1][k] - g[w][h-2][k] + 2*g[w-1][h][k] - g[w-2][h][k] - 4*g[w-1][h-1][k] + g[w-2][h-2][k-1];

But using the above formula, we get negative value for some w, h, k, which is obviously incorrect. :(
It seems like that I forgot to add something or am removing too much.