제출 #1264650

#제출 시각아이디문제언어결과실행 시간메모리
1264650piolk은행 (IZhO14_bank)C++20
100 / 100
269 ms14920 KiB
#include <bits/stdc++.h>
using namespace std;

int main(){
    //my first bitmask dp
    int n,m;
    cin>>n>>m;

    vector<int> salaries(n);
    vector<int> banknotes(m);

    for (int i=0;i<n;i++) cin>>salaries[i];
    for (int i=0;i<m;i++) cin>>banknotes[i];

    int subsets=(1<<m);

    vector<int> subsetSum(subsets,0);
    subsetSum[0]=0;

    for (int mask=1;mask<subsets;mask++){
        int lowestBit=mask & -mask;
        int j=0; //the number of the smallest bit
        while (lowestBit!=(1<<j)) j++;
        subsetSum[mask]=subsetSum[mask ^ lowestBit]+banknotes[j];
    }

    vector<vector<int>> goodSubsets(1007); // goodSubsets[sum]={all subsets with sum}

    for (int mask=1;mask<subsets;mask++){
        if (subsetSum[mask]<=1000) goodSubsets[subsetSum[mask]].push_back(mask);
    }

    vector<int> paid(subsets,-1); // paid[subset] - what prefix of salaries was paid with subset
    paid[0]=0;

    bool ok=false;

    for (int mask=0;mask<subsets;mask++){ //mask=subset of banknotes used
        if (paid[mask]==-1) continue;

        int next=paid[mask]; //next salary to pay after using banknotes mask;
        if (next>=n) continue;

        for (int subset:goodSubsets[salaries[next]]){ //all of the subsets with sum=salary
            if ((mask&subset)==0){ //none that have been used are being used again
                int newMask=mask|subset; //mask after using the banknotes
                paid[newMask]=max(paid[newMask],next+1);

                if (paid[newMask]==n) ok=true;
            }
        }
    }

    if (ok) cout<<"YES";
    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...