Submission #1089358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089358		vjudge1	Bank (IZhO14_bank)	C++17	100 / 100	165 ms	21932 KiB

bank

/**
 *    data : 09.07.2024  
 *     
**/
#include <bits/stdc++.h>
// #include "algo/turnikmen.h"

using namespace std;


#define int long long
#define bitt __builtin_popcountll
#define bitzero __builtin_clz

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

void fReopen () {
        #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        #endif
}

const int N = 2e5 + 4;
int n, m, a[N], b[N], ok, x; 
vector<int> used[N];
map<pair<int, int>, int> mp;
bool solve (int id, int res) {

        // cout << res << ' ' << id << '\n';
        if (id == n) {
        cout << "YES"; exit(0);
}  if (mp[{res, id}] == 1) return 0;
        bool ok = 0;
mp[{res, id}] =1 ;
        for (auto mask : used[a[id]]) {
                // cout << ' ' << (mask & res )<<  ' ' << mask << '\n';
                if ((mask & res) == 0) ok |= solve(id + 1, mask | res);
        }
        // cout << ok << '!';
        return ok;
}

signed main (/*  time : 9:17 AM   */) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

   //     fReopen();

        cin >> n >> m; 

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

        for (int mask = 0; mask < (1 << m); mask++) {
                int res = 0;
                for (int i = 0; i < m; i++) {
                        if (mask >> i & 1) res += b[i];
                }
             if ( res <= 1000)
                used[res].push_back(mask);
        }

        bool ok = 1;
        for (int i = 0; i < n && ok; i++) ok &= (used[a[i]].size() != 0);

        if (!ok) {
                cout << "NO\n";
                return 0;
        }       

        sort(a, a + n, [&] (int x, int y) {
                return (used[x].size()) < used[y].size();
        });
                
        // for (int i = 0; i < n; i++) {
        //         cout << a[i] << ' ';
        //         for (auto to : used[a[i]]) {
        //                 for (int j = 0; j < m; j++) {
        //                         cout << (to >> j & 1);
        //                 }
        //                 cout << ' ';
        //         }
        //         cout << endl;
        // }
        cout << (solve(0, 0) ? "YES\n" : "NO\n");

}

Compilation message (stderr)

bank.cpp: In function 'void fReopen()':
bank.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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