SRM314 div2 hard

方針が間違ってて何度もTLEした。
cache[すでに使ったフェンス(bit)]でメモれば一発。

#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

class GrasslandFencer
{
	public:

		vector<int> fences;
		double cache[(1<<16)];
		int n;

		double heron(int _a,int _b,int _c)
		{
			int d[3];
			d[0]=_a,d[1]=_b,d[2]=_c;
			sort(d,d+3);
			if(d[0]+d[1]<=d[2])
				return 0;

			double a=_a,b=_b,c=_c;
			double s=(a+b+c)/2.0;
			return sqrt(s*(s-a)*(s-b)*(s-c));
		}

		int popCount(int mask)
		{
			int r=0;
			for(int i=0;i<20;i++)
				if(mask & (1<<i))
					r++;
			return r;
		}
		
		double rec(int mask)
		{
			//printf("%d\n",popCount(mask));
		
			double &r=cache[mask];
			if(r!=-1)
			{
				;
			}
			else if(popCount(mask)<3)
			{
				r=0.0;
			}
			else
			{
				for(int i=0;i<n;i++)
					if(mask & (1<<i))
						for(int j=i+1;j<n;j++)
							if(mask & (1<<j))
								for(int k=j+1;k<n;k++)
									if(mask & (1<<k))
									{
										int m=(mask & (~(1<<i)) & (~(1<<j)) & (~(1<<k)));
										r=max(r,heron(fences[i],fences[j],fences[k])+rec(m));
									}
			}

			return r;
		}
		
		double maximalFencedArea(vector<int> _fences)
		{
			fences=_fences;
			n=fences.size();
			for(int i=0;i<(1<<n);i++)
				cache[i]=-1;

			return rec((1<<n)-1);
		}
};