Cherrypick
Time limit2sMemory limit512 MB
For each cell, find the axis-aligned square containing it that maximizes the minimum cherry sweetness minus the square of its side length.
- Level
Hard8 of 10
- Topics
- Matrix, Binary search, Prefix sum, Brute force
- Solved
- No attempts yet
Problem
SNUPC (SNU Patisserie Cafe) sells a famous cake. The cake is a square that can be divided into N rows and N columns. When the cake is cut into N2 square pieces of size 1 × 1, each piece has one cherry on top. The cherry on the piece in row i, column j has a sweetness of C**i,j. The cake is too large to eat at once, so the shop cuts out and sells a square region whose sides are parallel to the axes and whose corners have integer x- and y-coordinates. If the side length of the cut-out square is X, the piece is sold for X2 won.
Super-rich Corea visits the shop. Corea has already eaten too much food at a previous shop, so after buying a cake, Corea will eat only the single least sweet cherry on it. Corea also chooses one particular piece of the cake and will buy a cake that must include that piece.
Corea dislikes wasting money, so Corea wants to maximize the sweetness of the cherry eaten minus the cost of buying the cake. But Corea has no time to waste on such a trivial decision, so while Corea chooses the piece to include in the cake, you must compute the maximum value of (sweetness of the cherry Corea eats) minus (cost of the cake) over all choices Corea can make.
Input
The first line gives the number of rows and columns of the whole cake, N (1 ≤ N ≤ 1,000).
From the second line, N lines follow, each containing N integers C**i,j (1 ≤ C**i,j ≤ 1,000), the sweetness of the cherry on the piece in row i, column j.
Output
Print N integers separated by spaces over N lines.
The value printed as the j-th integer on the i-th line is the maximum of (sweetness of the cherry Corea eats) minus (cost of the cake) when buying a cake that includes the piece in row i, column j.