记录编号	459217	评测结果	AAAAAAA
题目名称	[HZOI 2014] 合并石子	最终得分	100
用户昵称	Hyoi_0Koto	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-10-12 20:19:53	内存使用	0.00 MiB

/*written by 0koto*/
#prag\
ma GCC optimize("Ofast")
#include<cstdio>
#include<cctype>
#include<iostream>
#define loop(i,j,k) for(register int i=j;i<=k;++i)
using namespace std;
inline void in(int &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(!(c-'-'))f=-1;c=getchar();}
    while (isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=f;
}
inline void out(int x){
    if(!x){putchar('0');return;}
    if(x<0)x=~x+1,putchar('-');
    char c[30]={0};
    while(x)c[++c[0]]=x%10+48,x/=10;
    while(c[0])putchar(c[c[0]--]);
}
const int inf=0x7effffff;
int n,a[201],s[201],a1=inf,a2=0;
int f1[201][201],f2[201][201];
inline void dp(){
	loop(len,2,n)loop(i,1,2*n-len+1){
		int j=i+len-1;
		f1[i][j]=inf,f2[i][j]=0;
		loop(k,i,j-1){
			f1[i][j]=min(f1[i][j],f1[i][k]+f1[k+1][j]+s[j]-s[i-1]);
			f2[i][j]=max(f2[i][j],f2[i][k]+f2[k+1][j]+s[j]-s[i-1]);
		}
	}
}
inline int koto(){
	freopen("stone2.in","r",stdin);
	freopen("stone2.out","w",stdout);
	in(n);
	loop(i,1,n) in(a[i]),s[i]=s[i-1]+a[i];loop(i,n+1,n*2)a[i]=a[i-n],s[i]=s[i-1]+a[i];
	dp();
	loop(i,1,n) a1=min(a1,f1[i][i+n-1]),a2=max(a2,f2[i][i+n-1]);
	out(a1),putchar('\n'),out(a2);
}
int zero=koto();
int main(){;}