牛客 Music Problem

完全背包相信大家都会做，但是Tn*3600的复杂度貌似不可过，所以我们用bitset优化背包即可。

注意bitset范围要开2*3600，因为有"<<a[i]"。

#include <bits/stdc++.h>
using namespace std;
int T,n;
int a[100005];
int main(){
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        for (register int i=1; i<=n; ++i) scanf("%d",&a[i]),a[i]%=3600;    
        bitset<7201>dp;
        for (register int i=1; i<=n; ++i)
        {
            dp|=(dp<<a[i])|(dp<<a[i]>>3600);
            dp[a[i]]=1;
        }
        if (dp[0]) puts("YES");
        else puts("NO");
    }
return 0;    
}