LeetCode Weekly Contest 115 : 956. Tallest Billboard

いまいち実行環境が良くわからん。
https://leetcode.com/contest/weekly-contest-114/problems/tallest-billboard/

問題

N要素の整数の集合Sが与えられる。
ここから互いに共通部分を持たない２つの部分集合を抜き出したとき、その総和が一致するようにしたい。
（いずれにも属さない要素があってもよい）

総和の最大値はいくつか。

解法

要素の総和がさほど大きくなく、要素数もさほど多くない。
そこで以下を求めていこう。
f(n,a,b) := 先頭n要素を２つの部分集合に振り分けたとき、片方の総和がa、もう片方の総和がbとなるようにできるか

このままでもO(N*sum(S)^2)かかるが一応間に合うっぽい？
要素を小さい順に処理すれば、最初の方はa,bの上限が小さいし、bitsetを使えばさらに実行時間を縮めることができる。

bitset<5100> B[5160];
bitset<5100> C[5160];

class Solution {
public:
int tallestBillboard(vector<int>& rods) {
	int N=rods.size();
	int i,j,mask;
	
	ZERO(C);
	ZERO(B);
	B[0][0]=C[0][0]=1;
	
	int sum=0;
	sort(ALL(rods));
	FORR(r,rods) {
		FOR(i,sum+1) C[i+r] |= B[i];
		FOR(i,sum+1) C[i] |= B[i]<<r;
		sum+=r;
		memmove(B,C,sizeof(B));
	}
	
	int ma=0;
	
	FOR(i,5010) if(B[i][i]) ma=i;
	return ma;
    
}

};

まとめ

Nの上限が20だったので、最初O(3^N)を試してTLEしてしまった。