Submission #831393

#	Time	Username	Problem	Language	Result	Execution time	Memory
831393		NoLove	Bank (IZhO14_bank)	C++14	100 / 100	362 ms	468 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>;
vector<int> a, b;
int n, m;
//int dp[20][1 << 20];
map<pair<int, vector<int>>, int> dp;
bool dfs(int pos, vector<int>& tmp) {
    if (pos == n) return true;
    if (dp.count(make_pair(pos, tmp))) return dp[make_pair(pos, tmp)];
    for (int mask = 1; mask < (1 << tmp.size()); mask++) {
        int total = 0;
        for (int j = 0; j < tmp.size(); j++)
            if (mask & (1 << j))
                total += tmp[j];
        if (total == a[pos]) {
            vector<int> tmp_new;
            for (int j = 0; j < tmp.size(); j++)
                if (!(mask & (1 << j)))
                    tmp_new.push_back(tmp[j]);
            if (dfs(pos + 1, tmp_new)) {
                    db(pos, total, a[pos], mask, bitset<6>(mask))
                    return dp[{pos, tmp}] = true;
            }
        }
    }
    return dp[{pos, tmp}] = false;
}

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);
    }
//    memset(dp, -1, sizeof(dp));
    cin >> n >> m;
    a.resize(n); b.resize(m);
    for (auto& i : a) cin >> i;
    for (auto& i : b) cin >> i;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    cout << (dfs(0, b) ? "YES" : "NO");
}

Compilation message (stderr)

bank.cpp: In function 'bool dfs(int64_t, std::vector<long int>&)':
bank.cpp:21:27: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for (int j = 0; j < tmp.size(); j++)
      |                         ~~^~~~~~~~~~~~
bank.cpp:26:31: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |             for (int j = 0; j < tmp.size(); j++)
      |                             ~~^~~~~~~~~~~~
bank.cpp:31:43: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   31 |                     return dp[{pos, tmp}] = true;
bank.cpp:35:27: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   35 |     return dp[{pos, tmp}] = false;
bank.cpp: In function 'int32_t main()':
bank.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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