Submission #567483

#TimeUsernameProblemLanguageResultExecution timeMemory
567483gg123_pe은행 (IZhO14_bank)C++14
100 / 100
266 ms10444 KiB
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
typedef pair<ll,ll> ii; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

#define ff first 
#define ss second 

const int N = 1005; 
const ll inf = 1e17 + 100; 


int n, m, a[22], b[22], dp[1<<20], sum[1<<20]; 
bool vis[1<<20]; 
set <int> s; 

int main(){
    cin >> n >> m; 

    f(i,1,n+1) {
        cin >> a[i], a[i] += a[i-1]; 
        s.insert(a[i]); 
    }

    f(i,1,m+1) cin >> b[i]; 

    f(i,1,1<<m){
        f(j,0,m) if(i&(1<<j)) sum[i] += b[j+1];
    }

    queue <int> q;
    q.push(0); 

    while(!q.empty()){
        int x = q.front(); q.pop(); 

        f(j,0,m){
            if(x&(1<<j)) continue; 

            int val = b[j+1] + sum[x], y = (1<<j) + x;

            if(s.count(val)) dp[y] = max(dp[y], 1 + dp[x]);
            else dp[y] = max(dp[y], dp[x]); 

            if(!vis[y]){
                vis[y] = 1; 
                q.push(y); 
            }
        }
    }
    f(i,1,1<<m){
        if(dp[i] == n){
            cout << "YES\n"; 
            return 0; 
        }
    }
    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...