제출 #831053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831053		NoLove	은행 (IZhO14_bank)	C++14	71 / 100	1083 ms	300 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;

bool dfs(int pos, vector<int>& tmp) {
    if (pos == n) return true;
    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 true;
            }
        }
    }
    return 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);
    }

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

컴파일 시 표준 에러 (stderr) 메시지

bank.cpp: In function 'bool dfs(int64_t, std::vector<long int>&)':
bank.cpp:19: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]
   19 |         for (int j = 0; j < tmp.size(); j++)
      |                         ~~^~~~~~~~~~~~
bank.cpp:24: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]
   24 |             for (int j = 0; j < tmp.size(); j++)
      |                             ~~^~~~~~~~~~~~
bank.cpp: In function 'int32_t main()':
bank.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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