CF1372E Omkar and Last Floor

Omkar is building a house. He wants to decide how to make the floor plan for the last floor. Omkar's floor starts out as $ n $ rows of $ m $ zeros ( $ 1 \le n,m \le 100 $ ). Every row is divided into intervals such that every $ 0 $ in the row is in exactly $ 1 $ interval. For every interval for every row, Omkar can change exactly one of the $ 0 $ s contained in that interval to a $ 1 $ . Omkar defines the quality of a floor as the sum of the squares of the sums of the values in each column, i. e. if the sum of the values in the $ i $ -th column is $ q_i $ , then the quality of the floor is $ \sum_{i = 1}^m q_i^2 $ . Help Omkar find the maximum quality that the floor can have.

N/A

N/A

The given test case corresponds to the following diagram. Cells in the same row and have the same number are a part of the same interval. The most optimal assignment is: The sum of the $ 1 $ st column is $ 4 $ , the sum of the $ 2 $ nd column is $ 2 $ , the sum of the $ 3 $ rd and $ 4 $ th columns are $ 0 $ , and the sum of the $ 5 $ th column is $ 4 $ . The quality of this floor plan is $ 4^2 + 2^2 + 0^2 + 0^2 + 4^2 = 36 $ . You can show that there is no floor plan with a higher quality.