Submission #745554

#	Time	Username	Problem	Language	Result	Execution time	Memory
745554		Omar_Alaraby	Bank (IZhO14_bank)	C++17	0 / 100	3 ms	340 KiB

bank

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_pbds;
 
void Omar_Alaraby(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}
 
#define cin2d(vec, n, m) for(int i = 0; i < n; i++) for(int j = 0; j < m && cin >> vec[i][j]; j++);
#define cout2d(vec , n , m) for(int i = 0; i < n; i++, cout << "\n") for(int j = 0; j < m && cout << vec[i][j] << " "; j++);
#define cout_map(mp) for(auto& [first, second] : mp) cout << first << " --> " << second << "\n";
#define put(s) return void(cout << s << dl);
#define Time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs" << "\n";
#define fixed(n) fixed << setprecision(n)
#define ceil(n, m) (((n) / (m)) + ((n) % (m) ? 1 : 0))
#define Num_of_Digits(n) ((int)log10(n) + 1)
#define all(vec) vec.begin(), vec.end()
#define rall(vec) vec.rbegin(), vec.rend()
#define sz(x) int(x.size())
#define ll long long
#define ull unsigned long long
#define dl "\n"
#define ordered_set tree<ll ,  null_type ,  less<> ,  rb_tree_tag ,  tree_order_statistics_node_update>
 
const ll Mod = 1e9 + 7;
 
template < typename T = int > istream& operator >> (istream &in, vector < T > &v) {
    for (auto &x : v) in >> x;
    return in;
}
 
template < typename T = int > ostream& operator << (ostream &out, const vector < T > &v) {
    for (const T &x: v) out << x << ' ';
    return out;
}

template < typename T = int, int Base = 1 > struct DSU {
    
    vector < T > parent, Gsize;

    DSU(int MaxNodes){
        parent = Gsize = vector < T > (MaxNodes + 5);
        for(int i = Base; i <= MaxNodes; i++)
          parent[i] = i, Gsize[i] = 1;
    }
    
    T find_leader(int node){
        return parent[node] = (parent[node] == node ? node : find_leader(parent[node]));
    }

    bool is_same_sets(int u, int v){
        return find_leader(u) == find_leader(v);
    }

    void union_sets(int u, int v){
        int leader_u = find_leader(u), leader_v = find_leader(v);
        if(leader_u == leader_v) return;
        if(Gsize[leader_u] < Gsize[leader_v]) swap(leader_u, leader_v);
        Gsize[leader_u] += Gsize[leader_v], parent[leader_v] = leader_u;
    }

    int get_size(int u){
        return Gsize[find_leader(u)];
    }
};

int n , m;
vector < int > person, bankNotes;
vector < vector < int > > valids;
vector < vector < int > > dp;

void build_adj(int val , int pos, int idx , int mask){
    if(!val)
        return void(valids[pos].push_back(mask));
    
    if(idx == m)
        return;

    build_adj(val, pos, idx + 1, mask);
    build_adj(val - bankNotes[idx], pos, idx + 1, mask | (1 << idx));
}

int can_reach(int idx, int mask){

    if(idx == n)
        return 1;

    int &ret = dp[idx][mask];
    if(~ret) return ret;

    ret = 0;
    for(int i = 0; i < sz(valids[idx]); i++){
        if(mask & valids[idx][i]) continue;
        ret |= can_reach(idx + 1, mask | valids[idx][i]);
    }

    return ret;
}
 
void Solve(){

    // int n; cin >> n;
    // vector < int > v(n);
    // vector < set < int > > adj(n + 1);
    // DSU < int > dsu(n);

    // for(int i=0; i<n; i++){
    //     cin >> v[i];
    //     adj[i + 1].emplace(v[i]);
    //     adj[v[i]].emplace(i + 1);
    //     dsu.union_sets(i + 1 , v[i]);
    // }

    // set < int > min_ans;
    // for(int i = 1; i<=n; i++){
    //     if(sz(adj[i]) == 1)
    //         min_ans.emplace(dsu.find_leader(i));
    // }

    // set < int > max_ans;
    // for(int i=1; i<=n; i++)
    //     max_ans.emplace(dsu.find_leader(i));

    // cout << sz(max_ans) - sz(min_ans) + (sz(min_ans) > 0) << ' ' << sz(max_ans) << dl;

    cin >> n >> m;

    person = vector < int > (n);
    bankNotes = vector < int >(m);
    cin >> person >> bankNotes;

    valids = vector < vector < int > > (n);
    dp = vector < vector < int > > (n, vector < int > (1 << m, -1));

    for(int i=0; i<n; i++)
        build_adj(person[i], i , 0, 0);

    cout << ((can_reach(0, 0))? "YES" : "NO") << dl;
}
 
int main(){
    Omar_Alaraby();
    // freopen("bank.in", "r", stdin);
    // freopen("bank.out", "w", stdout);
 
    int tc = 1;
    //cin >> tc;
 
    for(int i=1; i<=tc; i++){
        //cout << "Scenario #" << i << ":" << dl;
        Solve();
    }
 
    Time
    return 0;
}

Compilation message (stderr)

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

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