#include <bits/stdc++.h>
using namespace std;
const int N=50;
struct bigint{
int len,num[N];
bigint() {
memset(num,0,sizeof num);
len=0;
}
void read() {
string s;
cin>>s;
len=s.size();
for(int i=0; i<len; i++) num[i]=s[len-i-1]-'0';
}
void print() {
for(int i=len-1; i>=0; i--) cout<<num[i];
}
bool operator <= (const bigint &b)const {
if(len<b.len) return true;
if(len>b.len) return false;
for(int i=len-1; i>=0; i--)
if(num[i]!=b.num[i])
return num[i]<b.num[i];
return true;
}
bigint operator + (const bigint &b)const {
bigint result;
int G[N]={},len_ans=max(len,b.len);
for(int i=0; i<=len_ans; i++) {
result.num[i]=num[i]+b.num[i]+G[i];
if(result.num[i]>=10) {
result.num[i]-=10;
G[i+1]=1;
}
}
if(result.num[len_ans]==0) result.len=len_ans;
else result.len=len_ans+1;
return result;
}
bigint operator - (const bigint &b)const {
bigint result;
int W[N]={},len_ans=max(len,b.len);
for(int i=0; i<len_ans; i++) {
result.num[i]=num[i]-b.num[i]-W[i];
while(result.num[i]<0) {
result.num[i]+=10;
W[i+1]=1;
}
}
while(len_ans>=2 && result.num[len_ans-1]==0) len_ans--;
result.len=len_ans;
return result;
}
bigint operator * (const bigint &b)const {
bigint result;
memset(result.num,0,sizeof result.num);
int len_ans=len+b.len+1;
for(int i=0; i<len; i++)
for(int j=0; j<b.len; j++)
result.num[i+j]+=(num[i]*b.num[j]);
for(int i=0; i<len_ans; i++) {
result.num[i+1]+=(result.num[i])/10;
result.num[i]%=10;
}
while(len_ans>=2 && result.num[len_ans-1]==0) len_ans--;
result.len=len_ans;
return result;
}
bigint operator / (const bigint &b)const {
bigint XR,result;
XR.len=0;
memset(result.num,0,sizeof result.num);
for(int i=len-1; i>=0; i--) {
for(int j=XR.len-1; j>=0; j--) XR.num[j+1]=XR.num[j];
XR.num[0]=num[i];
if(XR.num[XR.len]!=0) XR.len++;
while(b<=XR) {
XR=XR-b;
result.num[i]++;
}
}
int len_ans=len;
while(len_ans>=2 && result.num[len_ans-1]==0) len_ans--;
result.len=len_ans;
return result;
}
};
int n,m;
bigint f[100][100],power[100],ans,val[100];
bigint max(bigint a,bigint b) {
if(a<=b) return b;
return a;
}
int main() {
scanf("%d%d",&n,&m);
power[0].len=1;power[0].num[0]=1;
bigint tmp;tmp.len=1;tmp.num[0]=2;
for(int i=1; i<=100; i++) power[i]=tmp*power[i-1];
while(n--) {
for(int i=1; i<=m; i++) val[i].read();
memset(f,0,sizeof f);
for(int i=1; i<=m; i++)
for(int j=m; j>=i; j--) {
f[i][j]=max(f[i][j],f[i-1][j]+power[m-(j-i+1)]*val[i-1]);
f[i][j]=max(f[i][j],f[i][j+1]+power[m-(j-i+1)]*val[j+1]);
}
bigint maxx;
for(int i=1; i<=m; i++) maxx=max(maxx,f[i][i]+power[m]*val[i]);
ans=ans+maxx;
}
ans.print();
return 0;
}
我人都调傻了,把高精换int答案是对的,所以应该是高精的锅。
样例都没过。