Link to my solution : https://ideone.com/4rRdS9
I'm basically precomputing the input, and for each cell that lies in x-d<=i && y-d<=j, I'll add it's cost to killed[i][j].
It's a classical problem, if there is anything that's not clear within my code. I'm willing to provide a more detailed explanation.
I estimated the complexity to be N*d^2. Isn't that ok enough for 3 seconds?