记录编号	330242	评测结果	AAAAA
题目名称	[NOIP 2003]数字游戏	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2016-10-26 11:07:34	内存使用	0.30 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#define file(x) "numgame."#x
typedef long long ll;
using std::max;
using std::min;
const int MAXN=60,M=15;
int n,m,a[MAXN],pre[MAXN];
ll f[MAXN][M],f2[MAXN][M],mn=1<<30,mx;
inline int gsum(int i,int j){
	int ret=pre[j]-pre[i-1];
	if(ret<0) ret+=(-ret+9)/10*10;
	return ret%10;
}
void dp(){
	for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f2[i][j]=1e9;
	for(int i=1;i<=n;i++) f[i][1]=f2[i][1]=gsum(1,i);
	for(int i=1;i<=n;i++) for(int j=2;j<=m;j++){
		for(int k=1;k<i;k++) {
			f[i][j]=max(f[i][j],f[k][j-1]*gsum(k+1,i));
			f2[i][j]=min(f2[i][j],f2[k][j-1]*gsum(k+1,i));
		}
	}
	mn=min(mn,f2[n][m]);
	mx=max(mx,f[n][m]);
}
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int c=1;c<=n;c++){
		a[n+1]=a[1];
		for(int i=1;i<=n;i++) a[i]=a[i+1];
		dp();
	}
	printf("%lld\n%lld",mn,mx);
}