1 #include <bits/stdc++.h> 2 #define _for(i,a,b) for(int i = (a);i < b;i ++) 3 typedef long long ll; 4 using namespace std; 5 inline ll read() 6 { 7 ll ans = 0; 8 char ch = getchar(), last = ' '; 9 while(!isdigit(ch)) last = ch, ch = getchar(); 10 while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); 11 if(last == '-') ans = -ans; 12 return ans; 13 } 14 inline void write(ll x) 15 { 16 if(x < 0) x = -x, putchar('-'); 17 if(x >= 10) write(x / 10); 18 putchar(x % 10 + '0'); 19 } 20 int N; 21 int a[309]; 22 int dp[309][309]; 23 int dp2[309][309]; 24 int pre[309]; 25 26 int main() 27 { 28 N = read(); 29 _for(i,0,N) 30 a[i] = a[i+N] = read(); 31 32 memset(dp,0,sizeof(dp)); 33 _for(i,0,2*N-1) 34 dp[i][i+1] = a[i]+a[i+1]; 35 36 memset(dp2,0,sizeof(dp2)); 37 _for(i,0,2*N-1) 38 dp2[i][i+1] = a[i]+a[i+1]; 39 40 pre[0] = a[0]; 41 _for(i,1,2*N) 42 pre[i] = pre[i-1]+a[i]; 43 44 for(int d = 3;d < N+1;d ++) 45 { 46 for(int i = 0;i < 2*N-d+1;i ++) 47 { 48 int j = i+d-1; 49 dp2[i][j] = 0x3f3f3f3f; 50 for(int k = i;k < j;k ++) 51 { 52 dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]+pre[j]-pre[i]+a[i]); 53 dp2[i][j] = min(dp2[i][j],dp2[i][k]+dp2[k+1][j]+pre[j]-pre[i]+a[i]); 54 } 55 } 56 } 57 58 int rnt = 0; 59 _for(i,0,N) 60 rnt = max(rnt,dp[i][i+N-1]); 61 62 int rnt2 = 0x3f3f3f3f; 63 _for(i,0,N) 64 rnt2 = min(rnt2,dp2[i][i+N-1]); 65 write(rnt2);printf(" "); 66 write(rnt); 67 return 0; 68 }