제출 #1129114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129114		liangjeremy	은행 (IZhO14_bank)	C++20	71 / 100	1044 ms	90668 KiB

bank

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// 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];
    }
    unordered_set<int>ms[n+1];
    for(int i=1; i<=n; i++){
        for(int mask=0; mask<(1<<m); mask++){
            int sum=0;
            for(int j=0; j<m; j++){
                if(mask&(1<<j)){
                    sum+=b[j];
                }
            }
            if(sum==a[i]){
                ms[i].insert(mask);
            }
        }
    }
    vector<vector<int>>dp(n+1,vector<int>((1<<m),0)); dp[0][0]=1;
    for(int i=0; i<n; i++){
        for(int j=0; j<(1<<m); j++){
            if(dp[i][j]==0) continue;
            for(auto x:ms[i+1]){
                if(x&j)continue;
                dp[i+1][x|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