记录编号	193184	评测结果	AAAAAAAAAA
题目名称	[NOIP 2007]矩阵取数游戏	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.939 s
提交时间	2015-10-14 07:34:40	内存使用	28.46 MiB

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <fstream>

using namespace std;
struct bignum{
	static const int MOD = 10000;
	int a[11], len;
	bignum(){
		fill(a, a + 11, 0);
		len = 1;
	}
	bignum operator= (const bignum &x){
		fill(a, a + 11, 0);
		len = x.len;
		for (int i = 0; i < 11; ++i)
			a[i] = x.a[i];
		return *this;
	}
	friend bool operator> (const bignum &a, const bignum &b){
		if (a.len != b.len)
			return a.len > b.len;
		for (int i = a.len - 1; i >= 0; --i)
			if (a.a[i] != b.a[i])
				return a.a[i] > b.a[i];
		return false;
	}
	friend bool operator< (const bignum &a, const bignum &b){
		return b > a;
	}
	bignum operator+ (const bignum &x){
		bignum c;
		c.len = max(len, x.len) + 1;
		int g = 0;
		for (int i = 0; i < c.len || g != 0; ++i){
			c.a[i] = a[i] + x.a[i] + g;
			g = c.a[i] / MOD;
			c.a[i] %= MOD;
		}
		while (c.len > 1 && c.a[c.len - 1] == 0)
			--c.len;
		return c;
	}
	bignum operator* (const int &x){
		bignum c;
		c.len = len + 2;
		int g = 0;
		for (int i = 0; i < c.len || g != 0; ++i){
			c.a[i] = a[i] * x + g;
			g = c.a[i] / MOD;
			c.a[i] %= MOD;
		}
		while (c.len > 1 && c.a[c.len - 1] == 0)
			--c.len;
		return c;
	}
	bignum operator+= (const bignum &x){
		return *this = *this + x;
	}
	bignum operator* (const bignum &b){
		bignum c;
		c.len = len + b.len + 1;
		for (int i = 0; i < len; ++i)
			for (int j = 0; j < b.len; ++j)
				c.a[i + j] += a[i] * b.a[j];
		for (int i = 0; i < c.len; ++i){
			c.a[i + 1] += c.a[i] / MOD;
			c.a[i] %= MOD;
		}
		while (c.a[0] > 1 && c.a[c.len - 1] == 0)
			--c.len;
		return c;
	}
	bignum operator*= (const bignum &x){
		return *this = *this * x;
	}
	bignum operator*= (const int &x){
		return *this = *this * x;
	}
};

const int MAX(85);
int n, m, map[MAX][MAX];
bignum dp[MAX][MAX][MAX], ans[MAX], out;

ostream& operator<< (ostream &out, const bignum &x){
	cout << x.a[x.len - 1];
	for (int i = x.len - 2; i >= 0; --i)
		printf("%04d", x.a[i]);
	return out;
}

bignum operator^ (bignum a, int n){
	bignum c;
	c.a[0]= 1;
	while (n){
		if (n & 1)
			c *= a;
		a *= a;
		n >>= 1;
	}
	return c;
}

main()
{
	freopen("game.in", "r", stdin);
	freopen("game.out", "w", stdout);
	bignum w2;
	w2.a[0] = 2;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			cin >> map[i][j];
	
	for (int l = m - 1; l >= 0; --l)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m - l + 1; ++j){
				bignum aa=dp[i][j][j+l+1]+((w2^(m-l))*map[i][j+l]),
				bb=dp[i][j-1][j+l]+(w2^(m-l))*map[i][j-1];
				if (aa < bb)
					dp[i][j][j + l] = bb;
				else
					dp[i][j][j + l] = aa;
			}
	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= m; ++j)
			if (dp[i][j][j] > ans[i])
				ans[i] = dp[i][j][j];
		out += ans[i];
	}
	
	cout << out;
//	for (; ; );
}