← All solutions

To solve this problem, it is useful to mentally rotate the city by 45 degrees. The problem then (essentially) asks for the maximum array sum in a subarray. This is a well-known problem that has a simple O(n²) solution (per query), based on computing prefix sums. The details (hidden in the “essentially” above) end up being slightly messier: since the city grid is discrete you can’t really rotate it 45 degrees and apply the maximum array sum solution. Rather, you should translate the maximum array sum solution to the rotated case.