Submission #1321656

#TimeUsernameProblemLanguageResultExecution timeMemory
1321656zhaoxwBank (IZhO14_bank)C++20
52 / 100
1093 ms4444 KiB
#include<bits/stdc++.h>
using namespace std;
int dp[1<<20],a[21],b[21],mp[1005*20],n,m,cnt = 1;
vector<int> subset[1005];
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
        if(!mp[a[i]]) mp[a[i]] = cnt++;
    }
    for(int i = 1;i <= m;i++)
        cin >> b[i];
    for(int mask = 0;mask < (1<<m);mask++)
    {
        int cur = 0;
        for(int j = 0;j < m;j++)
            if(mask&(1<<j)) cur += b[j+1];
        if(mp[cur]) subset[cur].push_back(mask);
    }
    for(int mask = 0;mask < (1<<m);mask++)
    {
        int cur = 0,ok = 0;
        for(int j = 0;j < m;j++)
            if(mask&(1<<j)) cur = max(cur,dp[mask^(1<<j)]);
        for(auto x:subset[a[cur+1]])
            if((x&mask) == x && dp[mask^x] == cur)
            {
                cur++;
                break;
            }
        dp[mask] = cur;
    }
    if(dp[(1<<m)-1] == n) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...