Submission #734711

#	Time	Username	Problem	Language	Result	Execution time	Memory
734711		teesla	Bank (IZhO14_bank)	C++14	19 / 100	111 ms	16752 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,0), resto(aa,0);

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

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

            int bit = 1LL << j;

            if((i&bit) == 0) continue;

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

                int aux = dp[i-bit], rest = resto[i-bit];

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

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

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

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