Coffee Central

There is a simple DP that tells you for a query dp[x][y] how many of a given item are in the range from (0,0) to (x,y). It's really quite trivial...just walk the grid, and dp[x][y] = dp[x][y-1] + dp[x-1][y] + location(x,y)? 1 : 0.

This means we can query between any rectangle (x1,y1) (x2,y2) using dp[x2][y2] - dp[x1][y2] - dp[x2][y1] + dp[x1][y1] (inclusion/exclusion). So how does that help us? We have manhattan distance, which forms diamonds, not rectangles!

So rotate the grid 45 degrees first, run the RP on the rotated grid, then perform queries for every location. and choose the biggest one. Grid is only 1000x1000 so fast enough. Algorithm: Medium Implementation:Medium