This $$$O(n^4) \rightarrow O(n)$$$ reduction looks genius, GPT just says:

// Deterministic O((q+1)*n) time and O(n) auxiliary space, where q is the
// number of distinct input x coordinates (including the source's x=0).
// The statement gives integer x in [-200,200], hence q<=401: linear here.

Ok. I have better solution! It's $$$O(1)$$$. We have $$$n \leq 50, k \leq 3000$$$ so it's $$$O(1)$$$.