记录编号	168268	评测结果	AAAAAAAAAA
题目名称	[NOIP 2007]矩阵取数游戏	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.350 s
提交时间	2015-07-02 21:13:07	内存使用	1.63 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
int MOD=1000000;
int N,m,M[90][90];
class miku
{
	public:
	int n;
	LL S[20];
	miku()
	{
		n=1;
		memset(S,0,sizeof(S));
	}
	void clear()
	{
			n=1;
		memset(S,0,sizeof(S));
	}
	void operator +=(const miku &a)
	{
		n=max(n,a.n)+1;
		for(int i=0;i<n;i++)
		{
			S[i]+=a.S[i];
			S[i+1]+=S[i]/MOD;
			S[i]%=MOD;
		}
		while(n>1&&S[n-1]==0) n--;
	}
	bool operator >(const miku &b)
	{
		if(n!=b.n) return n>b.n;
		else
		{
			for(int i=n-1;i>=0;i--)
				if(S[i]!=b.S[i]) return S[i]>b.S[i];
		}
		return 0;
	}
	void print()
	{
		printf("%lld",S[n-1]);
		for(int i=n-2;i>=0;i--) printf("%06lld",S[i]);
		printf("\n");
	}
	void operator =(int x)
	{
		n=1;
		S[0]=x;
	}
}s[90][90],v[90],Ans;
inline miku operator +(const miku &a,const miku &b)
{
	miku c;
	c.n=max(a.n,b.n)+1;
	for(int i=0;i<c.n;i++)
	{
	    c.S[i]+=a.S[i]+b.S[i];
		c.S[i+1]+=c.S[i]/MOD;
		c.S[i]%=MOD;
	}
	while(c.n>1&&c.S[c.n-1]==0) c.n--;
	return c;
}
inline miku operator * (const miku &a,const int &b)
{
	miku c;
	c.n=a.n;
	for(int i=0;i<c.n;i++)
	{
		c.S[i]+=a.S[i]*b;
		c.S[i+1]+=c.S[i]/MOD;
		c.S[i]%=MOD;
	}
	while(c.S[c.n]>0) c.n++;
	return c;
}
miku max1(miku a,miku b)
{
	if(a>b) return a;
	else return b;
}
void get()
{
	v[0]=1;
	for(int i=1;i<=m;i++)
		v[i]=v[i-1]*2;
}
void DP(int f[])
{
	miku ans;
	ans=0;
	for(int i=0;i<=m;i++)
		for(int j=0;j<=m;j++)
			s[i][j].clear();
	for(int i=0;i<=m;i++)
		for(int j=0;j<=m-i;j++)
		{
			if(i==0&&j==0) continue;
			if(i==0) s[i][j]=s[i][j-1]+v[i+j]*f[m-j+1];
			else if(j==0) s[i][j]=s[i-1][j]+v[i+j]*f[i];
			else s[i][j]=max1(s[i-1][j]+v[i+j]*f[i],s[i][j-1]+v[i+j]*f[m-j+1]);
			if(i+j==m) ans=max1(ans,s[i][j]);
		}
	Ans+=ans;
}
int main()
{
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	scanf("%d%d",&N,&m);
	for(int i=1;i<=N;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&M[i][j]);
	get();
	Ans=0;
	for(int i=1;i<=N;i++) DP(M[i]);
	Ans.print();
	return 0;
}