# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
745561 |
2023-05-20T11:26:15 Z |
Omar_Alaraby |
Bank (IZhO14_bank) |
C++17 |
|
587 ms |
86544 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;
}
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(){
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
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 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
11 ms |
8404 KB |
Output is correct |
6 |
Correct |
1 ms |
300 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
10 ms |
8404 KB |
Output is correct |
9 |
Correct |
9 ms |
8404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
940 KB |
Output is correct |
4 |
Correct |
2 ms |
1236 KB |
Output is correct |
5 |
Correct |
2 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
2 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
852 KB |
Output is correct |
10 |
Correct |
1 ms |
852 KB |
Output is correct |
11 |
Correct |
2 ms |
1236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
11 ms |
8404 KB |
Output is correct |
6 |
Correct |
1 ms |
300 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
10 ms |
8404 KB |
Output is correct |
9 |
Correct |
9 ms |
8404 KB |
Output is correct |
10 |
Correct |
1 ms |
296 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
296 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
724 KB |
Output is correct |
21 |
Correct |
1 ms |
468 KB |
Output is correct |
22 |
Correct |
2 ms |
940 KB |
Output is correct |
23 |
Correct |
2 ms |
1236 KB |
Output is correct |
24 |
Correct |
2 ms |
980 KB |
Output is correct |
25 |
Correct |
1 ms |
596 KB |
Output is correct |
26 |
Correct |
2 ms |
596 KB |
Output is correct |
27 |
Correct |
1 ms |
468 KB |
Output is correct |
28 |
Correct |
2 ms |
852 KB |
Output is correct |
29 |
Correct |
1 ms |
852 KB |
Output is correct |
30 |
Correct |
2 ms |
1236 KB |
Output is correct |
31 |
Correct |
22 ms |
12592 KB |
Output is correct |
32 |
Correct |
123 ms |
16680 KB |
Output is correct |
33 |
Correct |
59 ms |
33072 KB |
Output is correct |
34 |
Correct |
74 ms |
45392 KB |
Output is correct |
35 |
Correct |
80 ms |
49488 KB |
Output is correct |
36 |
Correct |
144 ms |
86468 KB |
Output is correct |
37 |
Correct |
18 ms |
12628 KB |
Output is correct |
38 |
Correct |
32 ms |
20812 KB |
Output is correct |
39 |
Correct |
37 ms |
37164 KB |
Output is correct |
40 |
Correct |
72 ms |
45412 KB |
Output is correct |
41 |
Correct |
145 ms |
86476 KB |
Output is correct |
42 |
Correct |
50 ms |
24876 KB |
Output is correct |
43 |
Correct |
63 ms |
37236 KB |
Output is correct |
44 |
Correct |
106 ms |
65996 KB |
Output is correct |
45 |
Correct |
29 ms |
16688 KB |
Output is correct |
46 |
Correct |
47 ms |
29012 KB |
Output is correct |
47 |
Correct |
114 ms |
65960 KB |
Output is correct |
48 |
Correct |
11 ms |
8492 KB |
Output is correct |
49 |
Correct |
10 ms |
8484 KB |
Output is correct |
50 |
Correct |
245 ms |
86544 KB |
Output is correct |
51 |
Correct |
68 ms |
45484 KB |
Output is correct |
52 |
Correct |
80 ms |
45432 KB |
Output is correct |
53 |
Correct |
587 ms |
45388 KB |
Output is correct |
54 |
Correct |
263 ms |
86504 KB |
Output is correct |
55 |
Correct |
229 ms |
86488 KB |
Output is correct |
56 |
Correct |
235 ms |
86476 KB |
Output is correct |
57 |
Correct |
228 ms |
86464 KB |
Output is correct |
58 |
Correct |
256 ms |
82444 KB |
Output is correct |