Submission #1267292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267292		brinleyhong	Bank (IZhO14_bank)	C++20	71 / 100	1070 ms	560 KiB

bank

// [BANK] - DP BITMASK
//05-09-2025

//Định nghĩa: dp[i][S] là trạng thái yes/no khi đến thằng thứ i thằng đầu tiên bằng tập S tờ tiền
//THCS: dp[i][0] = false (mọi 0<=i<=N)
//Công thức:
// **
//Kết quả: dp[n-1][S] (với S chạy từ 0 đến 2^n), ít nhất 1 thằng true

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

#define nl "\n"
#define sp " "
#define yes "YES"
#define no "NO"
const int maxn = 20;

int n, m, a[maxn+5], b[maxn+5], maxbit;
vector <int> v[maxn+5];

void precomp()
{
    cin >> n >> m;
    for (int i = 0; i<n; ++i) cin >> a[i];
    for (int i = 0; i<m; ++i) cin >> b[i];
    maxbit = 1<<m;
}

bool backtrack(int i, int val) //0 <= i < n
{
    if (i==n) return true;
    bool res = false;
    for (int j = 0; j<v[i].size(); ++j)
    {
        int h = v[i][j];
        int temp = val|h;
        if (temp == val+h)
        {
            res = res | backtrack(i+1, temp);
        }
    }
    return res;
}
void solve()
{
    //pc
    for (int i = 0; i<n; ++i)
    {
        for (int S = 0; S<maxbit; ++S)
        {
            int temp = 0;
            for (int j = 0; j<m; ++j)
            {
                if (S&(1<<j)) temp += b[j];
            }
            if (temp == a[i]) v[i].push_back(S);
        }
    }

//    for (int i = 0; i<n; ++i)
//    {s
//        for (int j = 0; j<v[i].size(); ++j) cout << i << sp << v[i][j] << nl;
//    }

    //backtrack
    if (backtrack(0, 0)) cout << yes;
    else cout << no;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    precomp();
    solve();

    return 0;
}

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