#include <bits/stdc++.h>
/*
author: aykhn
*/
using namespace std;
typedef long long ll;
#define OPT ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pss pair<long,long>
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount
#define print(v) for(int i = 0; i < v.size(); i++) cout << v[i] << " "; cout<<endl;
int n, m;
vector<int> a, b;
vector<int> pref;
bool f(int i, int mask, int s)
{
if (i == n) return true;
if (s > a[i]) return false;
if (s == a[i]) return f(i + 1, mask, 0);
if (!bpc(mask)) return false;
bool res = 0;
for (int j = 0; j < m; j++)
{
if (mask & (1 << j)) res |= f(i, mask ^ (1 << j), s + b[j]);
}
return res;
}
int main()
{
OPT;
cin >> n >> m;
a.assign(n, 0);
pref.assign(n, 0);
b.assign(m, 0);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];
for (int i = 1; i < n; i++)
{
pref[i] = pref[i - 1] + a[i];
}
cout << (f(0, (1 << m) - 1, 0) ? "YES" : "NO") << endl;;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
2 ms |
312 KB |
Output is correct |
4 |
Execution timed out |
1080 ms |
212 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
8 ms |
316 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
9 ms |
212 KB |
Output is correct |
8 |
Correct |
2 ms |
316 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Execution timed out |
1067 ms |
212 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
2 ms |
312 KB |
Output is correct |
4 |
Execution timed out |
1080 ms |
212 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |