5 solutions

  • 2
    @ 2024-2-5 20:22:09
    #include<map>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define N 21
    #define M 1000017
    using namespace std;
    map<int,int>mp;
    int n,m,t[N],d[M],dp[M];
    int main()
    {
    	int T;cin >> T;
    	while(T--)
    	{
    		cin >> n >> m;
    		for(int i = 0;i < n;i += 1)cin >> t[i];
    		mp.clear();
    		for(int i = 1;i <= m;i += 1){
    			cin >> d[i];
    			mp[d[i]] = 1;
    		}
    		memset(dp,0,sizeof(dp));
    		int ed = (1<<n)-1;
    		dp[0] = 1;
    		for(int s = 1;s <= ed;s += 1){
    			int tim = 0;
    			for(int i = 0;i < n;i += 1)
    				if((1<<i) & s){
    					dp[s] |= dp[s-(1<<i)];
    					tim += t[i];
    				}
    			if(mp[tim])dp[s] = 0;
    		}
    		if(dp[ed])cout << "YES" << endl;
    		else cout << "NO" << endl;
    	} 
    	return 0;
    }
    
    

    Information

    ID
    305
    Time
    1000ms
    Memory
    512MiB
    Difficulty
    7
    Tags
    (None)
    # Submissions
    142
    Accepted
    28
    Uploaded By