Submission #1274357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274357		bahy	은행 (IZhO14_bank)	C++20	100 / 100	424 ms	78928 KiB

bank

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

int n, m, a[20], b[20], sum[1 << 20], vis[20][1 << 20], cur;
bool dp[20][1 << 20];
map<int, vector<int>>subs;

bool calc(int ind, int mask){
    if(ind == n)return true;
    bool &ret = dp[ind][mask];
    if(vis[ind][mask] == cur)return ret;
    vis[ind][mask] = cur;
    ret = false;
    for(auto msk: subs[a[ind]]){
        if(!(mask & msk))ret |= calc(ind+1, mask | msk);
    }
    return ret;
}

void solve(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<m;i++)cin>>b[i];

    for(int mask = 0;mask < (1 << m); mask++){
        for(int i=0;i<m;i++){
            if(mask >> i & 1)sum[mask] += b[i];
        }
    }

    subs.clear();    
    for(int mask = 0; mask < (1 << m); mask++)subs[sum[mask]].push_back(mask);

    cur++;
    if(calc(0, 0))cout<<"YES\n";
    else cout<<"NO\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
    // cin>>t;
    while(t--){
        solve();
    }
}

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