#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test() int t;cin>>t;for(int test=1;test<=t;test++)
#define pb push_back
#define nl cout<<"\n"
#define F first
#define S second
#define all(x) x.begin(),x.end()
template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }
const ll MOD = 1000000007;
ll mod( ll n, ll m=MOD ){ n%=m,n+=m,n%=m;return n; }
const int MAXN = 1e5+5;
const int LOGN = 21;
const ll INF = 1e14;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
template<class T1, class T2> void add( T1 &x, T2 y, ll m = MOD )
{
x += y;
if( x >= m )
x -= m;
}
template<class T1, class T2> void sub( T1 &x, T2 y, ll m = MOD )
{
x -= y;
if( x < 0 )
x += m;
}
vector<int> possible[LOGN*1000];
bool dp[LOGN][1<<LOGN];
int sum[1<<LOGN];
int main()
{
#ifdef gupta_samarth
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
fastio();
int n,m;
cin>>n>>m;
vector<int>salary(n), notes(m);
for(int i=0;i<n;i++) cin>>salary[i];
for(int i=0;i<m;i++) cin>>notes[i];
sum[0] = 0;
for(int i=1;i<(1<<m);i++)
{
sum[i] = sum[i&(i-1)] + notes[__builtin_ctz(i)];
possible[sum[i]].pb(i);
}
dp[0][0] = true;
// dp[i][j] = satisfied first i people, using mask j notes
for(int i=0;i<n;i++)
{
for(int submask: possible[salary[i]])
{
int comp_sub = ((1<<m)-1)^submask;
for(int comp_mask=comp_sub;;comp_mask=(comp_mask-1)&comp_sub)
{
int mask = ((1<<m)-1)^comp_mask;
dp[i+1][mask] |= dp[i][mask^submask];
if( comp_mask == 0 ) break;
}
}
}
for(int mask=0;mask<(1<<m);mask++)
{
if( dp[n][mask] )
{
cout<<"YES";
return 0;
}
}
cout<<"NO",nl;
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
876 KB |
Output is correct |
2 |
Correct |
1 ms |
876 KB |
Output is correct |
3 |
Correct |
1 ms |
876 KB |
Output is correct |
4 |
Correct |
2 ms |
1260 KB |
Output is correct |
5 |
Correct |
22 ms |
11372 KB |
Output is correct |
6 |
Correct |
2 ms |
876 KB |
Output is correct |
7 |
Correct |
1 ms |
876 KB |
Output is correct |
8 |
Correct |
33 ms |
11500 KB |
Output is correct |
9 |
Correct |
20 ms |
10988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
876 KB |
Output is correct |
2 |
Correct |
1 ms |
876 KB |
Output is correct |
3 |
Correct |
1 ms |
876 KB |
Output is correct |
4 |
Correct |
1 ms |
876 KB |
Output is correct |
5 |
Correct |
1 ms |
876 KB |
Output is correct |
6 |
Correct |
1 ms |
876 KB |
Output is correct |
7 |
Correct |
1 ms |
876 KB |
Output is correct |
8 |
Correct |
1 ms |
876 KB |
Output is correct |
9 |
Correct |
1 ms |
876 KB |
Output is correct |
10 |
Correct |
1 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1260 KB |
Output is correct |
2 |
Correct |
2 ms |
1132 KB |
Output is correct |
3 |
Correct |
2 ms |
1388 KB |
Output is correct |
4 |
Correct |
2 ms |
1260 KB |
Output is correct |
5 |
Correct |
1 ms |
1260 KB |
Output is correct |
6 |
Correct |
2 ms |
1132 KB |
Output is correct |
7 |
Correct |
2 ms |
1132 KB |
Output is correct |
8 |
Correct |
2 ms |
1132 KB |
Output is correct |
9 |
Correct |
2 ms |
1260 KB |
Output is correct |
10 |
Correct |
2 ms |
1260 KB |
Output is correct |
11 |
Correct |
1 ms |
1004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
876 KB |
Output is correct |
2 |
Correct |
1 ms |
876 KB |
Output is correct |
3 |
Correct |
1 ms |
876 KB |
Output is correct |
4 |
Correct |
2 ms |
1260 KB |
Output is correct |
5 |
Correct |
22 ms |
11372 KB |
Output is correct |
6 |
Correct |
2 ms |
876 KB |
Output is correct |
7 |
Correct |
1 ms |
876 KB |
Output is correct |
8 |
Correct |
33 ms |
11500 KB |
Output is correct |
9 |
Correct |
20 ms |
10988 KB |
Output is correct |
10 |
Correct |
1 ms |
876 KB |
Output is correct |
11 |
Correct |
1 ms |
876 KB |
Output is correct |
12 |
Correct |
1 ms |
876 KB |
Output is correct |
13 |
Correct |
1 ms |
876 KB |
Output is correct |
14 |
Correct |
1 ms |
876 KB |
Output is correct |
15 |
Correct |
1 ms |
876 KB |
Output is correct |
16 |
Correct |
1 ms |
876 KB |
Output is correct |
17 |
Correct |
1 ms |
876 KB |
Output is correct |
18 |
Correct |
1 ms |
876 KB |
Output is correct |
19 |
Correct |
1 ms |
876 KB |
Output is correct |
20 |
Correct |
2 ms |
1260 KB |
Output is correct |
21 |
Correct |
2 ms |
1132 KB |
Output is correct |
22 |
Correct |
2 ms |
1388 KB |
Output is correct |
23 |
Correct |
2 ms |
1260 KB |
Output is correct |
24 |
Correct |
1 ms |
1260 KB |
Output is correct |
25 |
Correct |
2 ms |
1132 KB |
Output is correct |
26 |
Correct |
2 ms |
1132 KB |
Output is correct |
27 |
Correct |
2 ms |
1132 KB |
Output is correct |
28 |
Correct |
2 ms |
1260 KB |
Output is correct |
29 |
Correct |
2 ms |
1260 KB |
Output is correct |
30 |
Correct |
1 ms |
1004 KB |
Output is correct |
31 |
Correct |
31 ms |
13292 KB |
Output is correct |
32 |
Correct |
136 ms |
13804 KB |
Output is correct |
33 |
Correct |
39 ms |
18284 KB |
Output is correct |
34 |
Correct |
38 ms |
20076 KB |
Output is correct |
35 |
Correct |
41 ms |
21868 KB |
Output is correct |
36 |
Correct |
53 ms |
30060 KB |
Output is correct |
37 |
Correct |
28 ms |
13568 KB |
Output is correct |
38 |
Correct |
28 ms |
12780 KB |
Output is correct |
39 |
Correct |
123 ms |
18112 KB |
Output is correct |
40 |
Correct |
30 ms |
17772 KB |
Output is correct |
41 |
Correct |
37 ms |
21740 KB |
Output is correct |
42 |
Correct |
90 ms |
15596 KB |
Output is correct |
43 |
Correct |
43 ms |
20460 KB |
Output is correct |
44 |
Correct |
45 ms |
24044 KB |
Output is correct |
45 |
Correct |
50 ms |
14316 KB |
Output is correct |
46 |
Correct |
47 ms |
18412 KB |
Output is correct |
47 |
Correct |
42 ms |
24940 KB |
Output is correct |
48 |
Correct |
45 ms |
11628 KB |
Output is correct |
49 |
Correct |
18 ms |
10732 KB |
Output is correct |
50 |
Correct |
346 ms |
30388 KB |
Output is correct |
51 |
Correct |
228 ms |
20972 KB |
Output is correct |
52 |
Correct |
416 ms |
20436 KB |
Output is correct |
53 |
Correct |
794 ms |
20304 KB |
Output is correct |
54 |
Correct |
348 ms |
30516 KB |
Output is correct |
55 |
Correct |
348 ms |
30516 KB |
Output is correct |
56 |
Correct |
343 ms |
30656 KB |
Output is correct |
57 |
Correct |
373 ms |
30784 KB |
Output is correct |
58 |
Correct |
365 ms |
29632 KB |
Output is correct |