TLE 80 求助
查看原帖
TLE 80 求助
556362
Unnamed114514楼主2022/9/2 17:08
#include<bits/stdc++.h>
using namespace std;
struct Int{
	vector<int> s;
	inline void input(){
		char ch=getchar();
		while(isdigit(ch)){
			s.push_back(ch-'0');
			ch=getchar();
		}
	}
	inline void output(){
		for(int i=0,len=s.size();i<len;++i)
			putchar(s[i]+'0');
        putchar('\n');
	}
	inline Int operator +(const Int &o){
		vector<int> c=s,d=o.s;
		Int ans;
		ans.s.clear();
		int x=c.size(),y=d.size();
		if(x>y){
			swap(c,d);
			swap(x,y);
		}
		reverse(c.begin(),c.end());
		reverse(d.begin(),d.end());
		int k=0;
		for(int i=0;i<x;++i){
			ans.s.push_back((c[i]+d[i]+k)%10);
			k=(c[i]+d[i]+k)/10;
		}
		for(int i=x;i<y;++i){
			ans.s.push_back((d[i]+k)%10);
			k=(d[i]+k)/10;
		}
		if(k)
			ans.s.push_back(k);
		reverse(ans.s.begin(),ans.s.end());
		return ans;
	}
	inline void operator =(const Int &o){
		s=o.s;
	}
	inline bool operator >(const Int &o) const{
		int a=s.size(),b=o.s.size();
		if(a<b)
			return 0;
		if(a>b)
			return 1;
		for(int i=0;i<a;++i){
			int x=s[i],y=o.s[i];
			if(x<y)
				return 0;
			if(x>y)
				return 1;
		}
		return 0;
	}
};
inline Int to(string s){
	Int res;
	res.s.clear();
	for(int i=0,len=s.size();i<len;++i)
		res.s.push_back(s[i]-'0');
	return res;
}
inline Int qpow(Int x,int y){
	if(!y)
		return to("1");
	Int k=qpow(x,y>>1);
	if(y&1)
		return k*k*x;
	return k*k;
}
inline Int qmul(Int x,int y){
	if(!y)
		return to("0");
	Int k=qmul(x,y>>1);
	if(y&1)
		return k+k+x;
	return k+k;
}
int n,m,a[105][105];
Int dp[105][105][105],ans,maxn;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			for(int l=0;l<=j;++l){
				Int x=dp[i][j-1][(l-1>0)?l-1:0]+qmul(qpow(to("2"),j),a[i][l]),y=dp[i][j-1][l]+qmul(qpow(to("2"),j),a[i][m-j+l+1]);
				if(x>y)
					dp[i][j][l]=x;
				else
					dp[i][j][l]=y;
			}
	for(int i=1;i<=n;++i){
		maxn.s.clear();
		for(int j=1;j<=m;++j)
			if(dp[i][m][j]>maxn)
				maxn=dp[i][m][j];
		ans=ans+maxn;
	}
	ans.output();
	return 0;
}
2022/9/2 17:08
加载中...