TopCoder SRM 379 Div1 Medium FillBox

問題

一辺が2^iの立方体がcubes[i]個ずつある。
これを使ってheight x width x lengthの直方体を埋めたい。
直方体は隙間なく立方体に埋められている必要があり、立方体が直方体からはみ出たり、立方体同士が重なったりしてはならない。

直方体を埋めるのに必要な立方体の数の最小値を求めよ。

制約条件

cubesの要素数≦20
length,width,height≦10^6
cubes[i]≦10^6

方針

greedyに埋めていくだけ。
少し実装を工夫しないと大変になるかも。

ソースコード

ll n,ans;
vi c;
bool rec(int x,int y,int z){
	int t[]={x,y,z};
	sort(t,t+3);
	x=t[0]; y=t[1]; z=t[2];
	if(x==0)return 1;
	
	for(int i=n-1;i>=0;i--)if(c[i]&&x>=1<<i){
		int p=x/(1<<i), q=y/(1<<i), r=z/(1<<i);
		ll t=(ll)p*q*r, s;
//できるだけ大きい立方体から使う。
//大きい立方体がなくなったら、一個小さい立方体8個を大きい立方体の代わりに。
		for(int j=i;j>=0;j--){
			s=min(t,c[j]);
			ans+=s;
			c[j]-=s;
			t-=s;
			t*=8;
		}
		
		int xx=p*(1<<i), yy=q*(1<<i), zz=r*(1<<i);
		if(t)return 0;
//直方体の残りの部分は7個に分割できる。7個について、再帰的に埋める。
//どれかで失敗したら、元の直方体を埋めることはできない。
		rep(j,1<<3)if(j<7&&!rec(j&1?xx:x-xx,j&2?yy:y-yy,j&4?zz:z-zz))return 0;
		return 1;
	}
	return 0;
}
class FillBox {
	public:
	int minCubes(int length, int width, int height, vector <int> cubes) 
	{
		n=cubes.size();
		c.clear(); rep(i,n)c.pb(cubes[i]);
		ans=0;
		if(rec(length,width,height))return ans;
		return -1;
	}
};