记录编号	177721	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 打砖块	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.184 s
提交时间	2015-08-12 16:58:03	内存使用	8.56 MiB

#define MAXN 60UL

#include <cstdio>

int Ans,n,m,val[MAXN][MAXN],f[MAXN][MAXN][MAXN*10],s[MAXN][MAXN];

inline int MIN(int a,int b){
	return a<b?a:b;
}

inline int MAX(int a,int b){
	return a>b?a:b;
}

inline int in(){
	int x=0,c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar()){
		x=(x<<1)+(x<<3)+c-48;
	}
	return x;
}

int main(){
	freopen("brike.in","r",stdin);
	freopen("brike.out","w",stdout);
	n=in();m=in();
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			val[j][i]=in();
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			s[i][j]=s[i][j-1]+val[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		int p=(i-1)*(i-2)>>1;
		for(int j=0;j<=i;j++){
			int Max=MIN(m,((i-1)*i>>1)+j);//最多取Max个 
			for(int k=((1+j)*j>>1);k<=Max;k++){
				for(int l=j-1;l<i;l++){
					//l=-1
					if(k-j<((l+1)*l>>1)){
						break;
					}
					if(k-j>p+l){
						continue;
					}
					int tmp=f[i-1][l][k-j]+s[i][j];
					if(tmp>f[i][j][k]){
						f[i][j][k]=tmp;
					}
				}
			}
			if(f[i][j][m]>Ans){
				Ans=f[i][j][m];
			}
		}
	}
	printf("%d",Ans);
	return 0;
}