SRM397 div2 hard

メモ化再帰
rec(残っているマーブル、今使っているバッグの残り容量、まだ使っていないバッグ)をメモ化。

#include <cstring>
#include <vector>

using namespace std;

class CollectingMarbles
{
	public:

		int m,bC;
		vector<int> mW;
		int cache[(1<<13)][21][10];

		int rec(int marble,int cur,int left)
		{
			if(cache[marble][cur][left]!=-1)
				return cache[marble][cur][left];
			if(marble==0 || (cur==0 && left==0))
				return cache[marble][cur][left]=0;

			int r=(left!=0)?rec(marble,bC,left-1):0;
			for(int i=0;i<m;i++)
				if(marble & (1<<i) && mW[i]<=cur)
					r=max(r,rec(marble^(1<<i),cur-mW[i],left)+1);

			return cache[marble][cur][left]=r;
		}

		int mostMarbles(vector <int> marblesWeights, int bagCapacity, int numberOfBags)
		{
			bC=bagCapacity,m=marblesWeights.size();
			mW=marblesWeights;

			memset(cache,-1,sizeof(cache));
			return rec((1<<m)-1,bagCapacity,numberOfBags-1);
		}
};