Submission #1129537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129537		liangjeremy	Bank (IZhO14_bank)	C++20	100 / 100	568 ms	94996 KiB

bank

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lb;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,m; cin>>n>>m; vector<int>a(n+1); vector<int>b(m);
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    for(int i=0; i<m; i++){
        cin>>b[i];
    }
    vector<int>sum(1<<m); vector<int>prefix(n+1,0);
    for(int i=0; i<(1<<m); i++){
        for(int j=0; j<m; j++){
            if((1<<j)&i)sum[i]+=b[j];
        }
    }
    for(int i=1; i<=n; i++){
        prefix[i]=prefix[i-1]+a[i];
    }
    vector<vector<int>>dp(n+1,vector<int>(1<<m,0)); dp[0][0]=1; int tot=0;
    for(int i=0; i<n; i++){
        for(int mask=0; mask<(1<<m); mask++){
            if(!dp[i][mask])continue;
            for(int j=0; j<m; j++){
                if((1<<j)&mask)continue;
                if(sum[mask|(1<<j)]-prefix[i]==a[i+1])dp[i+1][mask|(1<<j)]=1;
                else dp[i][mask|(1<<j)]=1;
            }
        }
    }
    bool ans=false;
    for(int i=0; i<(1<<m); i++){
        if(dp[n][i])ans=true;
    }
    if(ans)cout<<"YES";
    else cout<<"NO";
}

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