제출 #1090592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1090592		sxwuel	은행 (IZhO14_bank)	C++17	100 / 100	539 ms	103024 KiB

bank

#include<bits/stdc++.h>
using namespace std;

const int mxn=25, inf=1e9+10;
int n, m;

int A[mxn], B[mxn];

int dp[mxn][(1<<20)+10];

int main(){
    cin>>n>>m;
    for(int i=0; i<n; i++)
        cin>>A[i];
    for(int i=0; i<m; i++)
        cin>>B[i];
    
    memset(dp, -1, sizeof(dp));
    //estou criando o elemento 0 com mask0 elementos
    dp[0][0]=0;
    for(int i=0; i<n; i++){ //pra cada prole
        for(int mask=0; mask<(1<<m); mask++){ //maskaras das banknotes
            if(dp[i][mask]==-1) continue;
            for(int j=0; j<m; j++){
                if(mask&(1<<j)) continue; //pra cada banknote não acessa
                if(dp[i][mask] + B[j] == A[i])
                    dp[i+1][mask|(1<<j)]=0;
                else
                    dp[i][mask|(1<<j)]=dp[i][mask]+B[j];
            }

        }
    }
    bool ans=false;
    for(int mask=0; mask<(1<<m); mask++)
        if(dp[n][mask]!=-1){
            ans=true;
            //cout<<mask<<endl;
        }
    cout<<(ans?"YES":"NO");
}

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