1 #include <cstdio>  2 #include <cstring>  3 #include <iostream>  4   5 struct Big_int  6 {  7     int s[35], idx;  8     Big_int()  9     { 10         idx = 0; 11         memset(s, 0, sizeof(s)); 12     } 13 }; 14  15 int n, m; 16 Big_int ans, a[81], f[81][81]; 17  18 inline void clear(Big_int &x) 19 { 20     x.idx = 0; 21     memset(x.s, 0, sizeof(x.s)); 22 } 23  24 inline Big_int Big(int x) 25 { 26     Big_int ret; 27     while(x) 28     { 29         ret.s[ret.idx] = x % 10; 30         x /= 10; 31         ret.idx++; 32     } 33     return ret; 34 } 35  36 inline bool operator > (const Big_int x, const Big_int y) 37 { 38     int i; 39     if(x.idx > y.idx) return 1; 40     else if(x.idx < y.idx) return 0; 41     else for(i = x.idx - 1; i >= 0; i--) 42         if(x.s[i] > y.s[i]) return 1; 43         else if(x.s[i] < y.s[i]) return 0; 44 } 45  46 inline Big_int Max(const Big_int x, const Big_int y) 47 { 48     return x > y ? x : y; 49 } 50  51 inline int max(int x, int y) 52 { 53     return x > y ? x : y; 54 } 55  56 inline Big_int operator + (const Big_int x, const Big_int y) 57 { 58     int i; 59     Big_int ret; 60     ret.idx = max(x.idx, y.idx) + 1; 61     for(i = 0; i < ret.idx; i++) 62     { 63         ret.s[i] += x.s[i] + y.s[i]; 64         ret.s[i + 1] += ret.s[i] / 10; 65         ret.s[i] %= 10; 66     } 67     while(!ret.s[ret.idx - 1] && ret.idx > 1) ret.idx--; 68     return ret; 69 } 70  71 inline Big_int operator * (const Big_int x, const Big_int y) 72 { 73     int i, j; 74     Big_int ret; 75     ret.idx = x.idx + y.idx; 76     for(i = 0; i < x.idx; i++) 77         for(j = 0; j < y.idx; j++) 78         { 79             ret.s[i + j] += x.s[i] * y.s[j]; 80             ret.s[i + j + 1] += ret.s[i + j] / 10; 81             ret.s[i + j] %= 10; 82         } 83     while(!ret.s[ret.idx - 1] && ret.idx > 1) ret.idx--; 84     return ret; 85 } 86  87 inline void print(const Big_int x) 88 { 89     int i; 90     if(!x.idx) printf("0"); 91     else for(i = x.idx - 1; i >= 0; i--) printf("%d", x.s[i]); 92     puts(""); 93 } 94  95 inline int read() 96 { 97     int x = 0, f = 1; 98     char ch = getchar(); 99     for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;100     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;101     return x * f;102 }103 104 inline Big_int dp(int x, int y, Big_int z)105 {106     if(f[x][y].idx) return f[x][y];107     if(x == y) return f[x][y] = a[x] * z;108     else return f[x][y] = Max(dp(x + 1, y, z * Big(2)) + a[x] * z, dp(x, y - 1, z * Big(2)) + a[y] * z);109 }110 111 int main()112 {113     int i, j;114     n = read();115     m = read();116     while(n--)117     {118         for(i = 1; i <= m; i++) a[i] = Big(read());119         for(i = 1; i <= m; i++)120             for(j = 1; j <= m; j++)121                 clear(f[i][j]);122         ans = ans + dp(1, m, Big(2));123     }124     print(ans);125     return 0;126 }