| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 745542 |
2023-05-20T10:44:20 Z |
vjudge1 |
Bank (IZhO14_bank) |
C++17 |
|
3 ms |
340 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
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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
