SRM442 div2 hard

差を保存するところまでは思いついたのに、残念。

#include <cstring>
#include <vector>
#define TOWER_MAX 250000

using namespace std;

class EqualTowers
{
	public:

		int n;
		vector<int> bricks;

		int cache[TOWER_MAX+1][50];

		int rec(int dif,int k)
		{
			if((k==n && dif!=0) || TOWER_MAX<dif)
				return -(1<<28);
			if(k==n && dif==0)
				return 0;
			if(cache[dif][k]!=-1)
				return cache[dif][k];

			int a=rec(dif+bricks[k],k+1);
			int b=rec(dif,k+1);
			int c=(dif<bricks[k])?rec(bricks[k]-dif,k+1)+dif:rec(dif-bricks[k],k+1)+bricks[k];

			return cache[dif][k]=max(a,max(b,c));
		}

		int height(vector <int> _bricks)
		{
			bricks=_bricks;
			n=bricks.size();
			memset(cache,-1,sizeof(cache));
			int ans=rec(0,0);

			return (ans<=0)?-1:ans;
		}
};