when I was solving this problem, I thought that Igor can go directly to any cell in any row above his current row as long as the Euclidean distance between that cell and his current cell is less than or equal to $$$d$$$
but in the last minutes of the contest, I realized that he can only go to any cell in the row that is exactly above him if he can reach it
with this, I found the solution for the problem faster and I got AC
now, I'm wondering, how to solve this problem if Igor can go to any row as long as he satisfies the constraints ?
for example, in the second testcase, Igor can go from the last row to the first row as mentioned in the image above
the result should be 70
what is the optimal solution for such a problem ?
I'm looking forward to see your ideas and solutions, and thanks ^_^
I don't think it's solvable because the cells that satisfy the distance constraint form half a circle, so each row has a different size so we can't do 2D prefix sum.
Yup, I thought about 2D prefix sum but found that it won't work
my idea to solve it is to modify the solution of the original problem by taking the $$$d$$$ rows above the current row, it would be $$$O(n * m * d)$$$ I guess, I'm looking if there is any optimization to reduce this time complexity or no
I also misread the problem to be this during the whole contest and failed to solve it (was wondering why div3F was so hard lol). I couldn't think of anything better than $$$O(n \cdot m \cdot d)$$$, although if it's changed to Manhattan distance instead of Euclidean distance then I think it can be solved efficiently using prefix sums on both rows and diagonals.
FFT?