#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &val, T nv) {
return val < nv ? (val = nv, true) : false;
}
template<class T>
bool chmin(T &val, T nv) {
return nv < val ? (val = nv, true) : false;
}
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int MAX_N = 20, MAX_M = 1001;
int n, m, a[MAX_N], b[MAX_N], sum[1<<MAX_N];
int dp[MAX_N][1<<MAX_N];
vector<int> sumask[MAX_N * MAX_M];
bool dfs(int cur, int mask) {
if (cur == n) return true;
if (dp[cur][mask] != -1) return dp[cur][mask];
dp[cur][mask] = 0;
for (int u : sumask[ a[cur] ])
if ((mask & u) == u && (dp[cur][mask] |= dfs(cur+1, mask ^ u)))
return true;
return false;
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for (int i = 0;i < n;++i)
cin >> a[i];
for (int i = 0;i < m;++i)
cin >> b[i];
for (int s = 1;s < 1<<m;++s) {
sum[s] = b[__lg(s)];
if (s != (s & -s)) sum[s] += sum[s ^ (1<<__lg(s))];
assert(sum[s] < MAX_N * MAX_M);
sumask[ sum[s] ].pb(s);
}
memset(dp, -1, sizeof(dp));
puts(dfs(0, (1<<m)-1) ? "YES" : "NO");
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
82924 KB |
Output is correct |
2 |
Correct |
45 ms |
82924 KB |
Output is correct |
3 |
Correct |
46 ms |
82924 KB |
Output is correct |
4 |
Correct |
46 ms |
83308 KB |
Output is correct |
5 |
Correct |
68 ms |
93292 KB |
Output is correct |
6 |
Correct |
46 ms |
82924 KB |
Output is correct |
7 |
Correct |
46 ms |
82924 KB |
Output is correct |
8 |
Correct |
64 ms |
92652 KB |
Output is correct |
9 |
Correct |
66 ms |
93036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
82924 KB |
Output is correct |
2 |
Correct |
47 ms |
82872 KB |
Output is correct |
3 |
Correct |
45 ms |
82924 KB |
Output is correct |
4 |
Correct |
45 ms |
82924 KB |
Output is correct |
5 |
Correct |
46 ms |
82924 KB |
Output is correct |
6 |
Correct |
46 ms |
82924 KB |
Output is correct |
7 |
Correct |
45 ms |
82924 KB |
Output is correct |
8 |
Correct |
46 ms |
82924 KB |
Output is correct |
9 |
Correct |
46 ms |
82924 KB |
Output is correct |
10 |
Correct |
46 ms |
82924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
83052 KB |
Output is correct |
2 |
Correct |
48 ms |
83052 KB |
Output is correct |
3 |
Correct |
48 ms |
83180 KB |
Output is correct |
4 |
Correct |
46 ms |
83052 KB |
Output is correct |
5 |
Correct |
47 ms |
83052 KB |
Output is correct |
6 |
Correct |
47 ms |
83080 KB |
Output is correct |
7 |
Correct |
48 ms |
83052 KB |
Output is correct |
8 |
Correct |
46 ms |
83052 KB |
Output is correct |
9 |
Correct |
47 ms |
83180 KB |
Output is correct |
10 |
Correct |
46 ms |
83180 KB |
Output is correct |
11 |
Correct |
46 ms |
83052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
82924 KB |
Output is correct |
2 |
Correct |
45 ms |
82924 KB |
Output is correct |
3 |
Correct |
46 ms |
82924 KB |
Output is correct |
4 |
Correct |
46 ms |
83308 KB |
Output is correct |
5 |
Correct |
68 ms |
93292 KB |
Output is correct |
6 |
Correct |
46 ms |
82924 KB |
Output is correct |
7 |
Correct |
46 ms |
82924 KB |
Output is correct |
8 |
Correct |
64 ms |
92652 KB |
Output is correct |
9 |
Correct |
66 ms |
93036 KB |
Output is correct |
10 |
Correct |
45 ms |
82924 KB |
Output is correct |
11 |
Correct |
47 ms |
82872 KB |
Output is correct |
12 |
Correct |
45 ms |
82924 KB |
Output is correct |
13 |
Correct |
45 ms |
82924 KB |
Output is correct |
14 |
Correct |
46 ms |
82924 KB |
Output is correct |
15 |
Correct |
46 ms |
82924 KB |
Output is correct |
16 |
Correct |
45 ms |
82924 KB |
Output is correct |
17 |
Correct |
46 ms |
82924 KB |
Output is correct |
18 |
Correct |
46 ms |
82924 KB |
Output is correct |
19 |
Correct |
46 ms |
82924 KB |
Output is correct |
20 |
Correct |
48 ms |
83052 KB |
Output is correct |
21 |
Correct |
48 ms |
83052 KB |
Output is correct |
22 |
Correct |
48 ms |
83180 KB |
Output is correct |
23 |
Correct |
46 ms |
83052 KB |
Output is correct |
24 |
Correct |
47 ms |
83052 KB |
Output is correct |
25 |
Correct |
47 ms |
83080 KB |
Output is correct |
26 |
Correct |
48 ms |
83052 KB |
Output is correct |
27 |
Correct |
46 ms |
83052 KB |
Output is correct |
28 |
Correct |
47 ms |
83180 KB |
Output is correct |
29 |
Correct |
46 ms |
83180 KB |
Output is correct |
30 |
Correct |
46 ms |
83052 KB |
Output is correct |
31 |
Correct |
69 ms |
93548 KB |
Output is correct |
32 |
Correct |
64 ms |
92780 KB |
Output is correct |
33 |
Correct |
70 ms |
93164 KB |
Output is correct |
34 |
Correct |
76 ms |
93548 KB |
Output is correct |
35 |
Correct |
80 ms |
94444 KB |
Output is correct |
36 |
Correct |
83 ms |
94216 KB |
Output is correct |
37 |
Correct |
72 ms |
94316 KB |
Output is correct |
38 |
Correct |
72 ms |
94060 KB |
Output is correct |
39 |
Correct |
64 ms |
91968 KB |
Output is correct |
40 |
Correct |
70 ms |
93932 KB |
Output is correct |
41 |
Correct |
74 ms |
93420 KB |
Output is correct |
42 |
Correct |
69 ms |
92524 KB |
Output is correct |
43 |
Correct |
72 ms |
94316 KB |
Output is correct |
44 |
Correct |
80 ms |
94336 KB |
Output is correct |
45 |
Correct |
66 ms |
93036 KB |
Output is correct |
46 |
Correct |
70 ms |
94316 KB |
Output is correct |
47 |
Correct |
75 ms |
93804 KB |
Output is correct |
48 |
Correct |
65 ms |
92652 KB |
Output is correct |
49 |
Correct |
64 ms |
92780 KB |
Output is correct |
50 |
Correct |
65 ms |
91828 KB |
Output is correct |
51 |
Correct |
63 ms |
92908 KB |
Output is correct |
52 |
Correct |
63 ms |
91920 KB |
Output is correct |
53 |
Correct |
63 ms |
91828 KB |
Output is correct |
54 |
Correct |
64 ms |
91828 KB |
Output is correct |
55 |
Correct |
64 ms |
91828 KB |
Output is correct |
56 |
Correct |
65 ms |
92096 KB |
Output is correct |
57 |
Correct |
270 ms |
92108 KB |
Output is correct |
58 |
Correct |
65 ms |
92096 KB |
Output is correct |