Submission #1287102

#TimeUsernameProblemLanguageResultExecution timeMemory
1287102michael12Bank (IZhO14_bank)C++20
0 / 100
20 ms39532 KiB
#include<bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
pair<int, int> dp[5000000];
int main(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for(auto ty : a){
        cin >> ty;
    }
    for(auto ty : b){
        cin >> ty;
    }
    memset(dp, -1, sizeof(dp));
    dp[0] = {0, 0};
    bool is = 0;
    for(int mask = 0; mask < (1 << m); mask++){
        for(int j = 0; j < m; j++){
            if(!(mask & (1 << j))) continue;
            int pre = mask ^ (1 << j);
            if(dp[pre].ff == -1) continue;
            int her = dp[pre].ss + b[j];
            int need = a[dp[mask].ff];
            if(her < need){
                dp[mask] = {dp[pre].ff, her};
            }
            if(her == need){
                dp[mask] = {dp[pre].ff + 1, 0};
            }
        }

        if(dp[mask].ff == n){
            is = 1;
        }

    }
    if(is){
        cout << "YES";
        return 0;
    }
    else{
        cout << "NO";
        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...