Submission #1128379

#TimeUsernameProblemLanguageResultExecution timeMemory
1128379ocasuBank (IZhO14_bank)C++20
100 / 100
159 ms16908 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long 


signed main(){
    int n,m; cin>>n>>m;
    vector<int> a(n+1,0);
    for (int i=1; i<=n; i++) cin>>a[i];
    vector<int> p(n+1,0);
    for (int i=1; i<=n; i++) p[i]=p[i-1]+a[i];
    vector<int> b(m,0);
    for (int i=0; i<m; i++) cin>>b[i];

    vector<int> covered((1<<(m)), 0), leftover((1<<(m)), 0);
    for (int S=0; S<(1<<m); S++){
        int sum=0;
        for (int i=0; i<m; i++) if (((1<<i)&(S))){
            sum+=b[i];
        }
        for (int i=0; i<m; i++) if (((1<<i)&(S))==0) {
            if (covered[S]<n and leftover[S]+b[i]==a[covered[S]+1]) {
                covered[S|(1<<i)] = max(covered[S|(1<<i)], covered[S]+1);
                leftover[S|(1<<i)] = sum + b[i] -p[covered[S|(1<<i)]];
            } else{
                covered[S|(1<<i)] = max(covered[S|(1<<i)], covered[S]);
                leftover[S|(1<<i)] = sum + b[i] -p[covered[S|(1<<i)]];
            }
        }
        //cout<<S<<' '<<covered[S]<<' '<<leftover[S]<<'\n';
    }
    if (covered[(1<<m)-1]==n){
        cout<<"YES"<<'\n';
    } else{
        cout<<"NO"<<'\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...