Submission #1314057

#TimeUsernameProblemLanguageResultExecution timeMemory
1314057gopalaBank (IZhO14_bank)C++20
100 / 100
369 ms90420 KiB
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define EB emplace_back
#define MP make_pair
#define all(o) (o).begin(), (o).end()
#define mset(m,v) memset(m,v,sizeof(m))
#define fr(i,n) for(ll i=0;i<n;++i)
#define endl '\n' 
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>

using ll = long long;
using ld = long double;
const int MOD = 1e9+7;
const int INF = 1e9;
const ld EPS = 1e-9;

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
    return out << "(" << a.x << ", " << a.y << ")";
}

template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
    out << "[";
    fr(i, sz(v)) {
        if(i) out << ", ";
        out << v[i];
    }
    return out << "]";
}
int n,m;
map<int,vi> mp;
int sal[20],ban[20];
int dp[20][(1<<20)];
int getsum(int mask){
    int ret=0;
    for(int i=0;i<m;i++){
        if((mask&(1<<i)))ret+=ban[i];
    }
    return ret;
}
int rec(int i,int mask){
    if(i==n)return 1;
    if(dp[i][mask]==-1){
        dp[i][mask] = 0;
        for(auto &m:mp[sal[i]]){
            if((mask&m)==0){
                dp[i][mask] |= rec(i+1,mask|m);
            }
        }
    }
    return dp[i][mask];
}
void solve(){
    cin>>n>>m;
    mset(dp,-1);
    for(int i=0;i<n;i++)cin>>sal[i];
    for(int i=0;i<m;i++)cin>>ban[i];
    for(int mask=0;mask<(1<<m);mask++){
        mp[getsum(mask)].push_back(mask);
    }
    if(rec(0,0))cout<<"YES\n";
    else cout<<"NO\n";
}
 
int main()
{
    cin.tie(0);cin.sync_with_stdio(0);
    cout.tie(0);cout.sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while (t--)solve();
    
    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...