#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define pb push_back
#define ii pair<int, int>
#define lol unsigned long long
#define lll __int128_t
#define fi first
#define se second
#define fou(i, a, b) for (int i = a; i <= b; ++i)
#define all(v) (v).begin(), (v).end()
#define MAX_N 10000000
#define el '\n'
#define BIT(mask, j) ((mask >> j) & 1)
#define MASK(x) (1LL << (x))
typedef unsigned long long ll;
const int mxN = 1e4 + 9;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)4e18 + 7LL;
const int dx[] = {0, 1, 0, -1, 3, 0, -3, 0, 2, 2, -2, -2, 1, 1, -1, -1};
const int dy[] = {1, 0, -1, 0, 0, 3, 0, -3, 1, -1, 1, -1, 2, -2, 2, -2} ;
struct DSU {
vector<int> par, rank;
DSU() {}
DSU(int n): par(n, -1), rank(n, -1) {}
int root(int u) {
return (par[u] < 0 ? u : par[u] = root(par[u]));
}
int sameSet(int u, int v) {
return root(u) == root(v);
}
int size(int u) {
return -par[root(u)];
}
int unite(int u, int v) {
int x = root(u);
int y = root(v);
if (x == y) return 0;
if (par[x] > par[y]) {
swap(x,y);
}
par[x] += par[y];
par[y] = x;
return 1;
}
};
int a[mxN], b[mxN];
pair<int, int> dp[(1LL << 20) + 9];
int dp2[mxN], ans[mxN];
int n, m;
map<int, int> mp;
void solve() {
bool kt = true;
fou(i, 1, n) {
memset(dp2, 0, sizeof dp2);
dp2[0] = 1;
fou(j, 1, m) {
for (int k = a[i]; k >= b[j]; --k) {
if (dp2[k] == 0 && dp2[k - b[j]] == 1) {
dp2[k] = 1; ans[k] = k - b[j];
}
}
}
int j = a[i];
bool ok = true;
while(j > 0) {
if (mp[j - ans[j]] == 0) {
ok = false; break;
}
mp[j - ans[j]]--;
j = ans[j];
}
if (!ok) {
kt = false;
// cout << i <<" ";
break;
}
}
if (kt) cout << "YES";
else cout <<"NO";
}
void solve2() {
dp[0] = {1, 0};
bool ok = false;
fou(mask, 0 , MASK(m) - 1) {
fou(i, 0, m - 1) {
if (dp[mask].fi == n) {
ok = true; break;
}
if (!BIT(mask, i)) {
ii p;
if (a[dp[mask].fi] == dp[mask].se + b[i + 1]) {
p = {dp[mask].fi + 1, 0};
} else {
p = {dp[mask].fi, dp[mask].se + a[i + 1]};
}
dp[mask ^ MASK(i)] = max(dp[mask ^ MASK(i)], p);
}
}
}
if (ok) cout << "YES";
else cout <<" NO";
}
int32_t main() {
if (fopen("bank.in", "r")) {
freopen("bank.in" ,"r", stdin);
freopen("bank.out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
fou(i, 1, n) cin >> a[i];
fou(i, 1, m) cin >> b[i];
//solve();
solve2();
return 0 ;
}
Compilation message
bank.cpp: In function 'int32_t main()':
bank.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
124 | freopen("bank.in" ,"r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
125 | freopen("bank.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
328 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
