Submission #1298805

#TimeUsernameProblemLanguageResultExecution timeMemory
1298805mikurakillBank (IZhO14_bank)C++20
100 / 100
550 ms43884 KiB
#include<iostream>
#include<unordered_map>
using namespace std;
unordered_map<int, pair<int, int>>maski[21]; // zdobyte, suma
int tab[20002];
int kwoty[20];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin>>n>>m;
    int sum = 0;
    for(int i=1; i<=n; i++){
        int a;
        cin>>a;
        sum += a;
        tab[sum] = 1;
    }
    for(int i=0; i<m; i++)
        cin>>kwoty[i];
    maski[0][0] = {0, 0};
    for(int bity=0; bity<m; bity++){
        for(auto M:maski[bity]){
            for(int i=0; i<m; i++){
                if(1 & (M.first>>i))
                    continue;
                int prop = M.first | (1<<i);
                int sumka = M.second.second + kwoty[i];
                maski[bity+1][prop] = max(maski[bity+1][prop], {M.second.first + tab[sumka], sumka});
                // cout<<prop<<' '<<M.second.first + tab[sumka]<<' '<<sumka<<"   ";
            }
            // cout<<'\n';
        }
        // cout<<'\n';
    }
    int idx = (1<<m)-1;
    if(maski[m][idx].first == n)
        cout<<"YES";
    else
        cout<<"NO";

    // for(int i=0; i<=sum; i++){
    //     cout<<i<<": "<<tab[i]<<'\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...