Submission #734718

#	Time	Username	Problem	Language	Result	Execution time	Memory
734718		teesla	Bank (IZhO14_bank)	C++14	100 / 100	132 ms	16844 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m;
    cin >> n >> m;

    vector<int> a(n), b(m);

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

    int aa = 1LL << m;

    vector<int> dp(aa), resto(aa);

    for(int i=1; i<aa; i++){

        //cout << i << endl;

        for(int j=0; j<m; j++){

            int bit = 1LL << j;

            if(!(i&bit)) continue;

            //cout << "bit " << bit << endl;

            if(dp[i-bit] == n){

                cout << "YES" << endl;
                return 0;
            }
            else{

                int aux = dp[i-bit], rest = resto[i-bit] + b[j];
                //cout << "rest " <<rest << endl;

                if(rest == a[aux]){
                    aux++;
                    rest = 0;
                }

                if(aux >= dp[i]){
                    dp[i] = aux;
                    resto[i] = rest;
                }
            }
        }

        //cout << "dp "<< dp[i] <<" resto " << resto[i] <<  endl; 
    }

    if(dp[aa-1] == n) cout << "YES" << endl;
    else cout << "NO" << endl;

    //cout << dp[aa-1] << endl;
    return 0;
}

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