Submission #1129534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129534		liangjeremy	Bank (IZhO14_bank)	C++20	71 / 100	1104 ms	176996 KiB

bank

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lb;
// freopen("visitfj.in", "r", stdin);
// freopen("visitfj.out", "w", stdout);

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<vector<int>>remain(n+1,vector<int>(1<<m,0));
    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++){
        tot+=a[i];
        for(int j=0; j<(1<<m); j++){
            int mask=0;
            for(int k=0; k<m; k++){
                if((1<<k)&j)mask+=b[k];
            }
            remain[i][j]=mask-tot;
        }
    }
    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(remain[i][mask|(1<<j)]==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: 0 / 29