제출 #547988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
547988		mgl_diamond	은행 (IZhO14_bank)	C++14	71 / 100	171 ms	14648 KiB

bank

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

#define ll long long
#define fi first
#define se second
#define ii pair<int, int>

template<class T> bool umax(T &a, T b) { return (a<b?a=b, 1:0); }
template<class T> bool umin(T &a, T b) { return (a>b?a=b, 1:0); }

vector<int> bit[1001];
int n, m, a[20], b[20], dp[2][1<<20];

int main() {
    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<(1<<m); ++i) {
        int sum=0;
        for(int j=0; j<m; ++j)
            if (i>>j&1)
                sum+=b[j];
        if (sum<=1000)
            bit[sum].push_back(i);
    }
    bool cur=1, nxt=0;
    dp[0][0]=1;
    for(int k=0; k<n; ++k) {
        cur^=1; nxt^=1;
        memset(dp[nxt], 0, sizeof(dp[nxt]));
//        cout << cur << "\n" << nxt << "\n";
        for(int i=0; i<(1<<m); ++i) if (dp[cur][i]>0)
            for(int j: bit[a[k]]) if ((i&j)==0) {
//                cout << j << "\n";
                dp[nxt][i+j]+=dp[cur][i];
            }
    }

    for(int i=0; i<(1<<m); ++i)
        if (dp[nxt][i]>0) {
            cout << "YES\n";
            return 0;
        }
    cout << "NO\n";
}

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