Submission #831050

#	Time	Username	Problem	Language	Result	Execution time	Memory
831050		NoLove	Bank (IZhO14_bank)	C++14	71 / 100	1069 ms	724 KiB

bank

/**
 *    author : Lăng Trọng Đạt
 *    created: 2023-08-19
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define int int64_t
using pii = pair<int, int>;



int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("hi.inp", "r")) {
        freopen("hi.inp", "r", stdin);
        freopen("hi.out", "w", stdout);
    }

    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (auto& i : a) cin >> i;
    for (auto& i : b) cin >> i;
    sort(a.begin(), a.end());
    // dp[i][mask] = true neu nhu i nguoi dau tien co the nhan du luong
    vector<vector<bool>> dp(n, vector<bool>(1 << m, 0));
    map<int, vector<int>> mp; // {val, mask}
    for (int mask = 1; mask < (1 << m); mask++) {
        int total = 0;
        for (int j = 0; j < m; j++)
            if ((1 << j) & mask)
                total += b[j];
        if (binary_search(a.begin(), a.end(), total)) {
            mp[total].push_back(mask);
            if (total == a[0]) dp[0][mask] = true;
        }
    }
    if (n == 1 and mp.count(a[0])) {
        cout << "YES";
        return 0;
    }
    for (int i = 0; i < n; i++) {
        for (int mask = 1; mask < (1 << m); mask++) {
            if (dp[i][mask]) continue;
            for (int mask2 : mp[a[i]]) {
//                cout << mask << " " << mask2 << " " << dp[i][mask] << "\n";
                for (int i = 0; i < m; i++) {
                    if (((1 << i) & mask2) and !((1 << i) & mask)) goto cnt;
                }
                if (i == 0 or dp[i - 1][mask ^ mask2]) {
                    dp[i][mask] = true;
                    break;
                }
                cnt:;
            }
        }
    }

    cout << (dp[n - 1][(1 << m) - 1] ? "YES\n" : "NO");
}

Compilation message (stderr)

bank.cpp: In function 'int32_t main()':
bank.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bank.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen("hi.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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