A long way to go

Title Description

Shuai often plays a matrix retrieval game with his classmates: for a given matrix of n \times mn × m, each element a {I, J} AI, j in the matrix is a non negative integer. The rules of the game are as follows:

1. One element must be taken from each row for each fetching. There are nn elements in total. After mm times, all elements in the matrix are taken;
2. Each element taken each time can only be the beginning or end of the line of the element;
3. Each retrieval has a score value, which is the sum of the scores of each row of retrieval. The score of each row of retrieval = the element value taken \ times 2^i × 2i, where ii represents the second retrieval (starting from 11);
4. The total score at the end of the game is the sum of mm scores.

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

I / O format

Input format:

The input file consists of n+1n+1 lines:

The 11th line is two integers nn and mm separated by spaces.

The 2~n+12 n+1 is a matrix of n \times mn × m, where each line has mm non negative integers separated by a single space.

Output format:

The output file contains only 11 lines, which is an integer, that is, the maximum score after the input matrix is fetched.

Example of input and output

Input example ා 1:copy

2 3
1 2 3
3 4 2

Output example:copy

82

Explain

NOIP 2007 improve the third question

Data range:

60% of the data meet the following requirements: 1 \ Le n,m \ Le 301 ≤ n,m ≤ 30, answer no more than 10 ^ {16} 1016
100% of the data meet the following requirements: 1 \ Le n,m \ Le 801 ≤ n,m ≤ 80, 0 \ Le a {I, J} \ Le 10000 ≤ ai,j ≤ 1000

AC Code:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef __int128 lll;
const int N = 90;
lll m, n, ans; 
lll dp[N][N], w[N][N], p[N];

void read (lll &x) {
    x = 0;
    int jud = 1;
    char c = getchar ();
    while (c < '0' || c > '9') {
        if (c == '-') jud = -1;
        c = getchar ();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar ();
    }
}

void print (lll x) {
    if (x < 0) {
        putchar ('-');
        x = -x;
    }
    if (x > 9) print (x / 10);
    putchar (x % 10 + '0');
}

int main () {
    read (n);
    read (m);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++)
      read (w[i][j]);
    p[0] = 1;
    for (int i = 1; i <= m; i++) p[i] = p[i - 1] * 2;
    for (int k = 1; k <= n; k++) {
        memset (dp, 0, sizeof (dp));
        dp[1][0] = 2 * w[k][1];
        dp[0][1] = 2 * w[k][m];
        for (int i = 0; i <= m; i++)
          for (int j = 0; j <= m - i; j++) {
          	if (i == 0 && j == 0) continue;
          	if (i == 0) {
          		dp[i][j] = dp[i][j - 1] + w[k][m - j + 1] * p[i + j];
          	} else if (j == 0) {
          		dp[i][j] = dp[i - 1][j] + w[k][i] * p[i + j];
          	} else {
          		dp[i][j] = max (dp[i - 1][j] + w[k][i] * p[i + j], dp[i][j - 1] + w[k][m - j + 1] * p[i + j]);
          	}
          }
        lll maxn = 0;
        for (int i = 0; i <= m; i++)
          maxn = max (maxn, dp[i][m - i]);
        ans += maxn;
    }
    print (ans);
}