제출 #1368618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368618		po_rag526	은행 (IZhO14_bank)	C++20	100 / 100	68 ms	14988 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back

const int inf=8e18;
const int N=(1LL<<21);
const int mod=998244353;
const double eps=1e-7;

int n,m;

int a[N],b[N];

vector<int>v[N];

bool memo[30][N];

bool f(int i,int p) {
    if(i==n+1) return true;
    if(memo[i][p]) return false;
    for(int mask:v[a[i]]) {
        if((mask & p)!=0)  continue;
        if(f(i+1,(p|mask))) {
            return true;
        }
    }
    memo[i][p]=1;
    return false;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    int sum=0,sum1=0;
    for(int i=1;i<=n;i++) {cin>>a[i];sum+=a[i];}
    for(int i=1;i<=m;i++) {cin>>b[i];sum1+=b[i];}
    if(sum1<sum) {
        cout<<"NO\n";
        return 0;
    }
    for(int mask=0;mask<(1<<m);mask++) {
        sum=0;
        for(int j=0;j<m;j++) {
            if((mask & (1<<j))) sum+=b[j+1];
        }
        v[sum].pb(mask);
    }
    if(f(1,0)) cout<<"YES\n";
    else cout<<"NO\n";
}

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