Submission #1264640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264640		piolk	Bank (IZhO14_bank)	C++20	0 / 100	1094 ms	8520 KiB

bank

#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<int> paid(subsets,0); // paid[subset] - what prefix of salaries was paid with subset
    paid[0]=0;

    for (int mask=0;mask<subsets;mask++){

        int next=paid[mask]; //next salary

        int av=(subsets-1) ^ mask; //the banknotes avaible after using subset mask banknotes

        for (int sub=av;sub>0;sub=(sub-1)&av){
            if (subsetSum[sub]==salaries[next]){ //we can pay the next salary
                int newMask=mask|sub; //after spending sub banknotes to pay
                paid[newMask]=next+1;
            }
        }
    }

    if (paid[subsets-1]==n) cout<<"YES";
    else cout<<"NO";


    return 0;
}

• Subtask 1: 0 / 19
• Subtask 2: 0 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29