제출 #1355859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1355859		Matjaz	은행 (IZhO14_bank)	C++20	100 / 100	222 ms	86628 KiB

bank

//
// Created by matjaz on 4/19/26.
//

#include<iostream>
#include <map>
#include<vector>
#include<string.h>
using namespace std;

int dp[1<<20][20];
map<int,vector<int> > sets;
vector<int> sums;

int N,M;
vector<int> a,b;

bool subset(int A,int B) {
    return (A & B) == A;
}

bool possible(int s, int x) {
    //cout << s << " " << x << endl;
    if (x == N) { return true;}
    if (dp[s][x] == -1) {
        bool res = false;
        vector<int> v = sets[a[x]];
        for (int i=0;i<v.size();i++) {
            if (subset(v[i], s)) {
                res = res || possible(s ^ v[i], x + 1);
            }
        }
        return dp[s][x] = res ? 1 : 0;
    } else return dp[s][x];
}


int main() {
    cin >> N >> M;
    a.assign(N, 0);
    b.assign(M, 0);

    memset(dp, -1, sizeof(dp));

    for (int i=0;i<N;i++) {cin >> a[i];}
    for (int i=0;i<M;i++) {cin >> b[i];}

    for (int i=0;i<N;i++) {
        if (sets.find(a[i]) == sets.end()) {sets[a[i]]= vector<int>();}

    }
    sums.assign(1<<M, 0);
    sums[0] = 0;
    for (int i=1;i<1<<M;i++) {
        int removed = i & -i;
        sums[i] = sums[i ^ removed] + b[__builtin_ctz(removed)];
        if (sets.count(sums[i]) == 1) {
            sets[sums[i]].push_back(i);
        }
    }

    cout << (possible((1<<M) - 1,0) ? "YES" : "NO") << endl;


    return 0;
}

• 서브태스크 1: 19 / 19
• 서브태스크 2: 25 / 25
• 서브태스크 3: 27 / 27
• 서브태스크 4: 29 / 29