제출 #1165920

#제출 시각아이디문제언어결과실행 시간메모리
1165920lidplf은행 (IZhO14_bank)C++20
0 / 100
6 ms1352 KiB
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define MOD2 998244353
using namespace std;
void solve(int cas){ 
    int n,m; cin>>n>>m;
    vector<ll> people(n), bank(m);
    for (auto& a: people) cin>>a;
    for (auto& a: bank) cin>>a;
    vector<vector<ll>> sm(1001);
    for (int i = 1; i < (1<<m); i++){
        ll s = 0;
        for (int j = 0; j < m; j++){
            if ((i>>j)&1) s+=bank[j];
        }
        sm[s].emplace_back(i);
    }
    vector<vector<bool>> dp(n+1, vector<bool> (1<<m));
    for (int i = 0; i < (1<<m); i++) dp[n][i] = true;
    for (int i = n - 1; i >= 0; i--){
        for (int mask = 0; mask < (1<<m); mask++){
            for (ll m1: sm[people[i]]){
                if ((m1&mask)==0){
                    dp[i][mask] = (dp[i][mask] || dp[i+1][mask|m1]);
                }
            }
        }
    }
    cout << (dp[0][0] ? "YES" : "NO") << '\n';
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    //cin>>t;
    for (int i = 1; i <= t; i++){
        solve(i);
    }
    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...