제출 #1123971

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123971		kam	은행 (IZhO14_bank)	C++20	44 / 100	54 ms	6980 KiB

bank

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

bool f = 0;
vector<int>a;
vector<bool>vis;
vector<vector<int>>gp(1e3 + 5);

void dfs(int mask, int u)
{
    if (u == -1)
    {
        f = 1;
        return;
    }
    for (int& v : gp[a[u]])
    {
        if ((v & mask) != v || vis[v]) continue;
        dfs(mask ^ v, u - 1);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m; cin >> n >> m;
    vector<int> b(m);
    a = vector<int>(n);
    vis = vector<bool>(m);
    for (int& i : a) cin >> i;
    for (int& i : b) cin >> i;
    for (int i = 1; i < (1 << m); i++)
    {
        int sum = 0;
        for (int j = 0; j < m; j++)
        {
            if (i & (1 << j))
            {
                sum += b[j];
            }
        }
        if(sum > 1e3) continue;
        gp[sum].push_back(i);
    }
    dfs((1 << m) - 1, n - 1);
    if (f) cout << "YES\n";
    else cout << "NO\n";
}

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