Submission #1280805

#TimeUsernameProblemLanguageResultExecution timeMemory
1280805iq500Bank (IZhO14_bank)C++20
25 / 100
1096 ms9640 KiB
//ghost rule - deco*27
#include <bits/stdc++.h>
#define int long long
using namespace std;

int a[21], b[21], pref[21];
int n, m; 
bool *dp;
int *vals;
bool ans=false;

bool f(int ind, int s){
    if(ind>=n) {ans=true; return 1;}
    if(dp[s]) return dp[s];

    bool ret=0;
    for(int i=0; i<m; i++){
        if(s&(1<<i)) continue;
        int add=s|(1<<i);
        if(vals[add]<pref[ind]) ret|=f(ind, add);
        else if(vals[add]==pref[ind]) ret|=f(ind+1, add);
    }
    return dp[s]=ret;
}

signed main()
{
    cin>>n>>m;
    dp=(bool*)calloc(1<<m, sizeof(bool));
    vals=(int*)calloc(1<<m, sizeof(int));

    for(int i=0; i<n; i++){
        cin>>a[i];
        pref[i]+=a[i];
        if(i!=0) pref[i]+=pref[i-1];
    }

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

    for(int i=0; i<(1<<m); i++){
        int add=0;
        for(int j=0; j<m; j++){
            if((1<<j)&i) add+=b[j];
        }
        vals[i]=add;
    }
    f(0, 0);
    /*for(int i=0; i<(1<<m); i++) cout<<i<<": "<<dp[i]<<"\n";
        cout<<"\n";*/
    if(ans) cout<<"YES";
    else cout<<"NO";

    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...