#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;
}
void Solve(){
int n, m; cin >> n >> m;
vector < int > people(n), bankNotes(m); cin >> people >> bankNotes;
vector < pair < int , int > > dp(1 << m, {0 , 0}); // { how many people , remain }
for(int mask = 1; mask < (1 << m); mask++){
for(int i = 0; i < m; i++){
if(mask & (1 << i)){
auto [idx , remain] = dp[mask ^ (1 << i)];
if(remain <= bankNotes[i])
remain += bankNotes[i];
if(remain == people[idx])
idx++, remain = 0;
if(idx == n)
put("YES");
dp[mask] = max(dp[mask], {idx , remain});
}
}
}
cout << "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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
101 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |