Submission #1280885

#TimeUsernameProblemLanguageResultExecution timeMemory
1280885iq500Bank (IZhO14_bank)C++20
100 / 100
227 ms16840 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; 
int *dp;
int *vals;
bool ans=false;

bool f(int ind, int s){

    if(ind>=n) {ans=true; return 1;}
    if(dp[s]!=-1){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);
        if(ret) break;
        else if(vals[add]==pref[ind]) ret|=f(ind+1, add);
        if(ret) break;
    }
    return dp[s]=ret;
}

signed main()
{
    cin>>n>>m;
    dp=(int*)malloc((1<<m)*sizeof(int));
    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++){
        dp[i]=-1;
        int add=0;
        for(int j=0; j<m; j++){
            if((1<<j)&i) add+=b[j];
        }
        vals[i]=add;
    }

    f(0, 0);

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