Submission #842422

#	Time	Username	Problem	Language	Result	Execution time	Memory
842422		raul2008487	Bank (IZhO14_bank)	C++17	100 / 100	86 ms	19032 KiB

bank

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define in insert
#define ld long double
#define ll long long
#define pii pair<ll,ll>
#define vl vector<ll>
#define mpr make_pair
#define fi first
#define se second
#define lg(a) __lg(a)
#define all(v) v.begin(),v.end()
//#define endl "\n"
using namespace std;
const int sz = 1e6+6;
const ll inf = 1000000005;
ll a[sz], b[sz];
void solve(){
    ll n,m,i,mask;
    cin>>n>>m;
    vector<pair<ll,ll>> dp((1<<m), {inf,0});
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    for(i=0;i<m;i++){
        cin>>b[i];
    }
    dp[0] = {0,0};
    for(i=0;i<(1<<m);i++){
        for(mask=0;mask<m;mask++){
            if(i & (1<<mask)){continue;}
            pair<ll,ll> cur = dp[i];
            if(cur.fi == inf){break;}
            ll f = cur.fi, s = cur.se;
            s += b[mask];
            if(s > a[f]){continue;}
            if(s == a[f]){
                f++;
                if(f == n){
                    cout << "YES" << endl;
                    return ;
                }
                s=0;
            }
            if(mpr(f,s) < dp[i | (1<<mask)]){
                dp[i | (1<<mask)] = {f,s};
            }
        }
    }
    cout << "NO" << endl;
}
int main(){
    ll t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}
/*
6 3
1 2 3 4 5 6
2
1 3 4 6
2 1 5 4

7 3
3 1 5 6 2 4 7
1
2 1 4 3



*/

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