NOIP '07 P3 - Removing Numbers from Matrix

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type

Shuai often plays a matrix game with his classmates: for a given n \times m matrix, each element a_{i,j} in the matrix is a non-negative integer. The rules of the game are as follows:

  1. Each step, one must remove one element from each row each time, for a total of n numbers removed. After m times, all elements of the matrix are removed;

  2. Each element removed each time can only be the beginning or end of a line;

  3. Each removal has a score value, which is the sum of the scores of the number removed in the rows. These scores are the value of the element to be removed times 2^i, where i represents the i-th removal (starting from 1);

  4. The total score at the end of the game is the sum of the scores obtained from the m times' removal.

Shuai would like to ask you to help write a program, for any matrix, you can find the maximum score after the game.

Input Specification

  • Line 1 contains two integers n and m.
  • Lines 2 \ldots n+1 contain the n \times m matrix, where each line has m non-negative integers separated by a single space each.

Output Specification

One intger, the maximum score.

Sample Input 1

2 3 
1 2 3
3 4 2

Sample Output 1

82

Explanation of Sample 1

  • The first time: the first element is taken from the first line, and the last element is taken from the second line. This time the score is 1\times 2^1+2\times 2^1=6
  • The second time: take the first element of both lines, this time the score is 2\times 2^2+3\times 2^2=20
  • Third time: score is 3\times 2^3+4\times 2^3=56. The total score is 6+20+56=82.

Sample Input 2

1 4 
4 5 0 5

Sample Output 2

122

Sample Input 3

2 10 
96 56 54 46 86 12 23 88 80 43 
16 95 18 29 30 53 88 83 64 67

Sample Output 3

316994

Constraints

60\% of the data satisfy 1 \leq n, m \leq 30, answer does not exceed 10^{16}.

100\% of the data satisfy 1 \leq n, m \leq 80, 0 \leq a_{i,j} \leq 1\,000.


Comments

There are no comments at the moment.