Triangle ranch

Title Description

Like everyone , Cows love change . They are imagining new pastures . Dairy architects Hei Want to build a triangular ranch with beautiful white fences . She has $n$ A board , The length of each piece $l_i$ Are integers. , She wanted to form a triangle with all the boards to make the pasture the largest .

Please help Hei Miss, build such a pasture , And calculate the area of the largest pasture .

Input format

The first $1$ That's ok ： An integer $n$;

The first $2$ To the first $(n+1)$ That's ok , One integer per row , The first $(i+1)$ The whole number of lines $l_i$ It means the first one $i$ The length of the board .

Output format

Only one integer ： Multiply the maximum pasture area by $100$ Then the ending result . If you can't build , Output $-1$.

Examples #1

The sample input #1

5
1
1
3
3
4

Sample output #1

692

Tips

Sample input and output 1 explain

$692=\text{Left behind}(100\times \text{Triangle area})$, This triangle is an equilateral triangle , Side length is $4$.

Data scale and agreement

about $100\%$ The data of , Guarantee $3\le n\le 40$,$1\le l_i\le 40$.

obvious $dfs$ The time complexity of is $O(3^{40})$

void dfs(int u,int A,int B,int C){
    
    if(u>n){
    
    	if(A+B>C && A+C>B && B+C>A){
    
	        double p = (A+B+C)/2;
	        double s = sqrt(p*(p-A)*(p-B)*(p-C));
	        ans = max(ans, (ll)(s*100));
        }
        return ;
    }
    dfs(u+1,A+a[u],B,C);
    dfs(u+1,A,B+a[u],C);
    dfs(u+1,A,B,C+a[u]);
}

Easy to think of $f[i][j][k]$ Before use $i$ A stick , The first 1 The side length of the strip is $j$, The first 2 The side length of the strip is $k$ Can the triangle of form .40 * 800 * 800 It is acceptable .

I encountered a big hole when I was writing , Some strange , There is no judgment 3 Border relations also A 了 , Is it data water ？

Of course, this question can be changed 2 dimension .

/* A: 10min B: 20min C: 30min D: 40min */ 
#include <iostream>
#include <stack>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){
    for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {
    if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=1e6+10;
int n,m,_;
int a[50],f[50][810][810];
double ans,sum;
double area(double a,double b){
    
    double c = sum-a-b;
    double p = (a+b+c)/2;
    double s = sqrt(p*(p-a)*(p-b)*(p-c));
    return s;
}

void solve(){
    
    cin>>n;
    fo(i,1,n){
    
        cin>>a[i];
        sum+=a[i];
    }
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
    
        for(int j=sum/2;j>=0;j--){
    
            for(int k=sum/2;k>=0;k--){
    
                f[i][j][k] |= f[i-1][j][k];
                if(j-a[i]>=0){
    
                    f[i][j][k] |= f[i-1][j-a[i]][k];
                }
                if(k-a[i]>=0){
    
                    f[i][j][k] |= f[i-1][j][k-a[i]];
                }
            }
        }
    }
    ans = -1;
	for(int k=1;k<=n;k++){
    
		for(int i=sum/2;i>0;i--)
			for(int j=sum/2;j>0;j--)
			{
    
				if(!f[k][i][j]) continue;
				ans=max(ans,area(i,j));// Update answers  
			}
	}
	if(ans!=-1){
    
		cout<<(ll)(ans*100)<<endl;		
	}
	else
    cout<<ans<<endl;
}

int main(){
    
	solve();
	return 0;
}