Submission #889003

#TimeUsernameProblemLanguageResultExecution timeMemory
889003ByeWorldBank (IZhO14_bank)C++14
52 / 100
1069 ms20968 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
#define int long long 
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 2e6+20;
const int LOG = 20;
const int MOD = 1e9+7;
const int SQRT = 520;
const int INF = 1e18;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;

int n, m;
int a[25], b[25];
int dp[25][MAXN];

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=m; i++) cin >> b[i];
    dp[0][0] = 1;
    for(int i=1; i<=n; i++){
        for(int j=0; j<(1<<m); j++){
            for(int k=0; k<j; k++){
                if((j&k) != k || dp[i-1][k]==0) continue;

                int num = j^k, sum = 0;
                for(int v=0; v<m; v++){
                    if((num>>v) & 1) sum += b[v+1];
                }
                if(sum==a[i]) dp[i][j] = 1;
            }
        }
    }
    bool ans = 0;
    for(int i=0; i<(1<<m); i++) ans |= dp[n][i];
    cout << (ans ? "YES\n" : "NO\n");
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...