Submission #1128376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128376		ocasu	Bank (IZhO14_bank)	C++20	19 / 100	145 ms	16840 KiB

bank

#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-p[covered[S|(1<<i)]];
            } else{
                covered[S|(1<<i)] = max(covered[S|(1<<i)], covered[S]);
                leftover[S|(1<<i)] = sum-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';
    }
}

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