제출 #686478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
686478		Chal1shkan	은행 (IZhO14_bank)	C++14	100 / 100	692 ms	19540 KiB

bank

# include <bits/stdc++.h>

# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x  << " = " << x << endl; 

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ll maxn = 1e6 + 1e5;
const ll inf = 1e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};

using namespace std;

int n, m;
vector <int> x[23];
int inv[maxn];
int a[23];
int b[23];
bool dp[23][maxn];

void ma1n (/* SABR */)
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= m; ++i)
    {
        cin >> b[i];
    }
    for (int mask = 0; mask < (1LL << m); ++mask)
    {
        int sum = 0;
        for (int i = 0; i < m; ++i)
        {
            if (mask & (1LL << i)) sum += b[i + 1];
            else inv[mask] |= (1LL << i);
        }
        for (int i = 1; i <= n; ++i)
        {
            if (sum == a[i]) x[i].pb(mask);
        }
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j : x[i])
        {
            int mask = inv[j];
            for (int sub = mask; ; sub = (sub - 1) & mask)
            {
                if (dp[i - 1][sub])
                {
                    dp[i][j | sub] = 1;
                }
                if (sub == 0) break;
            }
        }
    }
    for (int mask = 0; mask < (1LL << m); ++mask)
    {
        if (dp[n][mask]) 
        {
            cout << "YES" << nl;
            return;
        }
    }
    cout << "NO" << nl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("file.in", "r", stdin);
//  freopen("file.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << ' ';
        ma1n();
    }
    return 0;
}

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