제출 #1369705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369705		norrawichzzz	은행 (IZhO14_bank)	C++20	71 / 100	1100 ms	82512 KiB

bank

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

const int mask = (1<<20);
int mem[20][mask];

int a[30], b[30], n,m;

int fnd(int idx, int vst) {
    if (idx == n) return true;

    if (vst == (1<<m)-1) return false;

    if (mem[idx][vst] != -1) return mem[idx][vst];

    int ok=0;
    for (int i=0; i<(1<<m); i++) {
        if (i&vst) continue;

        int sm=0;
        for (int j=0; j<m; j++) {
            if (i & (1<<j)) {
                sm+=b[j];
            }
        }

        if (sm == a[idx]) {
            ok = max(ok, fnd(idx+1, (vst|i)));
        }
    }
    return mem[idx][vst] = ok;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    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 i=0; i<20; i++) for (int j=0; j<(1<<20); j++) mem[i][j] = -1;

    if (fnd(0, 0)) cout<< "YES";
    else cout<< "NO";
}

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