제출 #1231836

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231836		hitsuuj	은행 (IZhO14_bank)	C++20	100 / 100	438 ms	260588 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define inf LLONG_MAX
#define ti tuple<int,int,int>
const int lim=20000;
void bine(int x){
    for(int j=0;j<7;j++){
        if(x&(1<<j)) cout<<1;
        else cout<<0;
    }
    cout<<endl;
}
signed main(){
    int n,m;cin>>n>>m;
    vector<int>a(n+10);for(int i=1;i<=n;i++)cin>>a[i];
    vector<int>b(m+10);for(int i=0;i<m;i++)cin>>b[i];
    vector<int>sum[lim+10];
    for(int i=0;i<(1<<m);i++){
        int cur=0;
        for(int j=0;j<m;j++){
            if(i&(1<<j)) cur+=b[j];
        }
        sum[cur].pb(i);
    }
    int dp[n+10][1<<m];
    memset(dp,0,sizeof(dp));
    set<int>nx;
    for(auto x:sum[a[1]]){
        dp[1][x]=1;
        nx.insert(x);
        if(n==1){
            cout<<"YES";
            return 0;
        }
    }
    int sn=a[1];
    for(int i=2;i<=n;i++){
        for(auto prev:sum[sn]){
            for(auto x:sum[a[i]]){
                if(!(x&prev) && dp[i-1][prev]){
                    dp[i][(x|prev)]=1;
                    if(i==n){
                        cout<<"YES";
                        return 0;
                    }
                }
            }
        }
        sn+=a[i];
    }
    cout<<"NO";

}

// dp[i][taken]
// reach 1 dengan mask taken 

// 1. whether the b can make the n 
// 2. 10! brute force 
// 3. 
// 4.


// 11
// 12
// 13 -> kalau gaada
// 14 harus sama semua 

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