# 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];

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 () {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; 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);
}

Added by rklapwijk on Wed, 01 Jan 2020 19:47:47 +0200