```cpp
/*
Big Integer Template
By NaCly_Fish
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define k m-(r-l)
#define N 503
using namespace std;
struct BigInt{
int num[N];
int size;
bool negative;
bool operator < (const BigInt& a) const{
if(a.negative&&!negative) return false;
if(negative&&!a.negative) return true;
bool f = negative;
for(int i=size;i>=1;--i){
if(a.num[i]==num[i]) continue;
if(f) return num[i]>a.num[i];
else return num[i]<a.num[i];
}
return false;
}
bool operator > (const BigInt& a) const{
if(a.negative&&!negative) return true;
if(negative&&!a.negative) return false;
bool f = negative;
for(int i=size;i>=1;--i){
if(a.num[i]==num[i]) continue;
if(!f) return num[i]>a.num[i];
else return num[i]<a.num[i];
}
return false;
}
bool operator == (const BigInt& a) const{
if(negative!=a.negative) return false;
if(size!=a.size) return false;
for(int i=size;i>=1;--i)
if(num[i]!=a.num[i]) return false;
return true;
}
};
BigInt newBigInt(string n){
int t = 0;
BigInt a;
memset(a.num,0,sizeof(a.num));
a.size = n.length();
if(n[0]=='-'){
t = 1;
a.size--;
}
for(int i=1;i<=a.size;++i)
a.num[i] = n[a.size-i+t]-'0';
a.negative = (t==0)?false:true;
return a;
}
BigInt toBigInt(int a){
BigInt b = newBigInt("0");
int l = 1;
if(a<0){
a = -a;
b.negative = true;
}
while(a){
b.num[l] = a%10;
a /= 10;
++l;
}
b.size = l-1;
return b;
}
const BigInt ZERO = newBigInt("0");
const BigInt ONE = newBigInt("1");
const BigInt TWO = newBigInt("2");
const BigInt TEN = newBigInt("10");
const BigInt neg_one = newBigInt("-1");
void print(BigInt a){
int l = a.size;
if(a.negative) putchar('-');
for(int i=l;i>=1;--i)
putchar(a.num[i]+'0');
}
BigInt add(BigInt a,BigInt b);
BigInt subtract(BigInt a,BigInt b);
BigInt multiply(BigInt a,BigInt b){
int t,l;
if(a==ZERO||b==ZERO) return ZERO;
BigInt c = ZERO;
for(int i=1;i<=a.size;++i){
for(int j=1;j<=b.size;++j){
t = a.num[i]*b.num[j];
c.num[i+j-1] += t;
}
}
l = a.size+b.size-1;
for(int i=1;i<=l;++i){
if(c.num[i]<10) continue;
t = c.num[i]/10;
c.num[i] %= 10;
c.num[i+1] += t;
}
c.size = l;
if(c.num[l+1]!=0) c.size++;
c.negative = a.negative^b.negative;
return c;
}
BigInt add(BigInt a,BigInt b){
BigInt c = ZERO;
if(a.negative&&b.negative){
a.negative = false;
b.negative = false;
c = add(a,b);
c.negative = true;
return c;
}else if(a.negative&&!b.negative){
a.negative = false;
c = subtract(b,a);
return c;
}else if(!a.negative&&b.negative){
b.negative = false;
c = subtract(a,b);
return c;
}
int l = max(a.size,b.size);
for(int i=1;i<=l;++i)
c.num[i] = a.num[i]+b.num[i];
for(int i=1;i<=l;++i){
if(c.num[i]<10) continue;
c.num[i+1]++;
c.num[i] -= 10;
}
c.size = l;
if(c.num[l+1]!=0) c.size++;
return c;
}
BigInt _divide(BigInt a,int b){
bool flag = false;
if(b<0){
flag = true;
b = -b;
}
BigInt c = ZERO;
if(a<toBigInt(b)) return c;
int l,n = a.size;
l = n;
while(a.num[n]<b&&l>=1){
a.num[n-1] += (a.num[n]<<3)+(a.num[n]<<1);
a.num[n] = 0;
--n;
}
for(int i=n;i>=1;--i){
if(a.num[i]>=b){
c.num[i] = a.num[i]/b;
a.num[i] %= b;
}
a.num[i-1] += (a.num[i]<<3)+(a.num[i]<<1);
}
c.size = n;
c.negative = a.negative^flag;
return c;
}
BigInt subtract(BigInt a,BigInt b){
BigInt c = ZERO;
if(a.negative&&!b.negative){
a.negative = false;
c = add(a,b);
c.negative = true;
return c;
}else if(a.negative&&b.negative){
a.negative = false;
b.negative = false;
return subtract(b,a);
}else if(!a.negative&&b.negative){
b.negative = false;
c = add(a,b);
c.negative = false;
return c;
}
if(a<b){
c = subtract(b,a);
c.negative = true;
return c;
}else if(a==b) return c;
int l = max(a.size,b.size);
for(int i=1;i<=l;++i)
c.num[i] = a.num[i]-b.num[i];
for(int i=1;i<=l;++i){
if(c.num[i]>=0) continue;
c.num[i] += 10;
c.num[i+1]--;
}
while(!c.num[l]) --l;
if(l==0) l = 1;
c.size = l;
return c;
}
BigInt power(BigInt a,int t){
bool flag = false;
BigInt b = ONE;
if(t&1&&a.negative) flag = true;
while(t){
if(t&1) b = multiply(a,b);
a = multiply(a,a);
t >>= 1;
}
a.negative = flag;
return b;
}
BigInt _mod(BigInt a,int b){
BigInt c = _divide(a,b);
c = multiply(toBigInt(b),c);
c = subtract(a,c);
return c;
}
int n,m;
int num[82];
BigInt ans,p[82],f[82][82];
BigInt dp(int l,int r){
if(!(f[l][r]==neg_one)) return f[l][r];
if(r-l>=1){
BigInt a,b;
a = add(multiply(toBigInt(num[l]),p[k]),dp(l+1,r));
b = add(dp(l,r-1),multiply(toBigInt(num[r]),p[k]));
if(a>b) f[l][r] = a;
else f[l][r] = b;
}
else f[l][r] = multiply(toBigInt(num[l]),p[k]);
return f[l][r];
}
int main(){
ans = ZERO;
scanf("%d%d",&n,&m);
p[0] = ONE;
for(int i=1;i<=m;++i) p[i] = multiply(p[i-1],TWO);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j) scanf("%d",&num[j]);
for(int i=0;i<=81;++i)
for(int j=0;j<=81;++j)
f[i][j] = neg_one;
ans = add(ans,dp(1,m));
}
print(ans);
return 0;
}
```
```
by NaCly_Fish @ 2018-11-15 23:50:40
前面很长一段都是高精度板子,应该没错吧qaq
by NaCly_Fish @ 2018-11-15 23:51:33
@[NaCly_Fish](/space/show?uid=115864) 大佬,您TG组多少分?自测
by Skeleton @ 2018-11-16 00:04:26
@[Skeleton](/space/show?uid=59558) 我菜爆了,只有290分 QAQ
by NaCly_Fish @ 2018-11-16 01:17:12
@[NaCly_Fish](/space/show?uid=115864) 啊,大佬,我本应该和您一个分,结果D1T1类似积木大赛做过,没有印象,T了3点,旅行第一遍的代码60,改完交卷的4分。我想剁了自己的手
by Skeleton @ 2018-11-16 01:20:41
高精是不可能写的,这辈子都不可能写的(
```cpp
#include<cstdio>
inline __int128_t max(__int128_t a,__int128_t b){return a>=b?a:b;}
void outnum(__int128_t x){if(x>9)outnum(x/10);putchar(x%10+'0');}
int main()
{
int N,M,a[81],l,i;
__int128_t f[81][81],ans = 0;
scanf("%d%d",&N,&M);
while(N--)
{
for(i=1;i<=M;i++)scanf("%d",a+i), f[i][i] = (a[i]<<=1);
for(l=2;l<=M;l++)
for(i=1;i<=M-l+1;i++)
f[i][i+l-1] = max(f[i][i+l-2]*2+a[i+l-1],f[i+1][i+l-1]*2+a[i]);
ans += f[1][M];
}
outnum(ans);
return 0;
}
```
by xenonex @ 2018-11-16 07:58:25
@[xenonex](/space/show?uid=86061) orz谢谢大佬
by NaCly_Fish @ 2018-11-16 17:07:21
就您,还萌新?大佬中的大佬吧
by KokiNiwa @ 2019-02-12 17:54:42
~~我居然在和2018年的神鱼写同一道题~~
by LTb_ @ 2019-07-16 21:59:47
考古%%鱼
by 羽儇 @ 2019-09-06 18:44:57