# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
745543 | 2023-05-20T10:48:34 Z | vjudge1 | Bank (IZhO14_bank) | C++17 | 0 ms | 212 KB |
#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 < vector < int > > valids; vector < vector < int > > dp; int can_reach(int idx, int mask){ if(idx == n) return true; 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; vector < int > person(n), bankNotes(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++){ for(int mask = 1; mask < (1 << m); mask++){ ll sum = 0; for(int note = 0; note < m; note++){ if(mask & (1 << note)) sum += bankNotes[note]; } if(sum == person[i]) valids[i].push_back(mask); } } 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |