View Code of Problem 1033

/*
Author: 2486
Memory: 1000 KB		Time: 79 MS
Language: G++		Result: Accepted
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=40+5;
int n;
int a[maxn];
bool dp[800][800];//dp[i][j]中代表一条边为i,一条边为j的情况是否存在
int main() {
    while(~scanf("%d",&n)) {
        int sum=0;
        for(int i=0; i<n; i++) {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        memset(dp,false,sizeof(dp));
        dp[0][0]=true;
        int Max=-1;
        for(int i=0; i<n; i++) {
            for(int j=sum/2; j>=0; j--) {
                for(int k=j; k>=0; k--) {
                    if((j>=a[i]&&dp[j-a[i]][k])||(k>=a[i]&&dp[j][k-a[i]])) {
                        dp[j][k]=true;
                        int m=sum-j-k;
                        if(dp[j][k]&&(m+j>k)&&(m+k>j)&&(k+j>m)) {
                            double p=(m+j+k)/2.0;
                            int t=(int)(sqrt(p*(p-m)*(p-j)*(p-k))*100);
                            Max=max(Max,t);
                        }
                    }
                }
            }
        }

        printf("%d\n",Max);
    }
    return 0;
}