제출 #1129113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129113		liangjeremy	은행 (IZhO14_bank)	C++20	71 / 100	1086 ms	20804 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];
    }
    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;
            vector<pair<int,int>>ava;
            for(int k=0; k<m; k++){
                if(j&(1<<k))continue;
                ava.push_back({b[k],1<<k});
            }
            for(int k=0; k<(1<<ava.size()); k++){
                int cur=0; int mask=0;
                for(int q=0; q<ava.size(); q++){
                    if(k&(1<<q)) {
                        cur+=ava[q].first; mask|=ava[q].second;
                    }
                }
                if(cur==a[i+1])dp[i+1][j|mask]=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