TopCoder SRM 807 : Div2 Hard Flagpole

典型すぎる…。
https://community.topcoder.com/stat?c=problem_statement&pm=17035&rd=18702

問題

整数列Sが与えられる。
Sの部分集合のうち、総和がLより大きくH未満となるのは何通りか。

解法

Sのサイズが40以下なので、半分全列挙すればよい。

class Flagpole {
	public:
	ll hoge(vector<int> S,ll v) {
		int A=S.size()/2;
		int B=S.size()-A;
		
		vector<ll> C;
		int i,mask;
		FOR(mask,1<<B) {
			ll sum=0;
			FOR(i,B) if(mask&(1<<i)) sum+=S[i];
			C.push_back(sum);
		}
		sort(ALL(C));
		ll ret=0;
		FOR(mask,1<<A) {
			ll sum=0;
			FOR(i,A) if(mask&(1<<i)) sum+=S[i+B];
			ret+=lower_bound(ALL(C),v-sum+1)-C.begin();
		}
		return ret;
		
	}
	
	long long build(vector <int> segments, long long LO, long long HI) {
		return hoge(segments,HI)-hoge(segments,LO);
		
	}
}

まとめ

Div2とはいえこの回簡単すぎないか？