//Author: Xzirium
//Time and Date: 00:23:49 01 August 2021
//Optional FAST
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")
//Required Libraries
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
//Required namespaces
using namespace std;
using namespace __gnu_pbds;
//Required defines
#define endl '\n'
#define READ(X) cin>>X;
#define READV(X) long long X; cin>>X;
#define READAR(A,N) long long A[N]; for(long long i=0;i<N;i++) {cin>>A[i];}
#define rz(A,N) A.resize(N);
#define sz(X) (long long)(X.size())
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define FORI(a,b,c) for(long long a=b;a<c;a++)
#define FORD(a,b,c) for(long long a=b;a>c;a--)
//Required typedefs
template <typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template <typename T> using ordered_set1 = tree<T,null_type,greater<T>,rb_tree_tag,tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
//Required Constants
const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);
const long long INIT=(long long)(1e6+1);
const long double PI=3.14159265358979;
// Required random number generators
// mt19937 gen_rand_int(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 gen_rand_ll(chrono::steady_clock::now().time_since_epoch().count());
//Required Functions
ll power(ll b, ll e)
{
ll r = 1ll;
for(; e > 0; e /= 2, (b *= b) %= MOD)
if(e % 2) (r *= b) %= MOD;
return r;
}
ll modInverse(ll a)
{
return power(a,MOD-2);
}
//Work
int main()
{
// #ifndef ONLINE_JUDGE
// if (fopen("INPUT.txt", "r"))
// {
// freopen ("INPUT.txt" , "r" , stdin);
// //freopen ("OUTPUT.txt" , "w" , stdout);
// }
// #endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
clock_t clk;
clk = clock();
//-----------------------------------------------------------------------------------------------------------//
READV(N);
READV(M);
READAR(salary,N);
READAR(banknotes,M);
vector<pll> dp((1<<M),{-1,-1});
dp[0]={0,0};
FORI(mask,0,(1<<M))
{
FORI(note,0,M)
{
if((mask&(1<<note))==0 && dp[mask].fi!=-1)
{
ll p=(mask|(1<<note));
ll val=dp[mask].se+banknotes[note];
if(val<salary[dp[mask].fi])
{
dp[p]={dp[mask].fi,val};
}
else if(val==salary[dp[mask].fi])
{
dp[p]={dp[mask].fi+1,0};
}
}
}
if(dp[mask].fi==N)
{
cout<<"YES"<<endl;
return 0;
}
}
cout<<"NO"<<endl;
//-----------------------------------------------------------------------------------------------------------//
clk = clock() - clk;
cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
716 KB |
Output is correct |
5 |
Correct |
81 ms |
16692 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
9 ms |
16716 KB |
Output is correct |
9 |
Correct |
80 ms |
16740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
312 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
2 ms |
588 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
2 ms |
460 KB |
Output is correct |
7 |
Correct |
2 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
2 ms |
460 KB |
Output is correct |
10 |
Correct |
2 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
716 KB |
Output is correct |
5 |
Correct |
81 ms |
16692 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
9 ms |
16716 KB |
Output is correct |
9 |
Correct |
80 ms |
16740 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
308 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
312 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
2 ms |
460 KB |
Output is correct |
21 |
Correct |
2 ms |
460 KB |
Output is correct |
22 |
Correct |
2 ms |
460 KB |
Output is correct |
23 |
Correct |
2 ms |
588 KB |
Output is correct |
24 |
Correct |
2 ms |
588 KB |
Output is correct |
25 |
Correct |
2 ms |
460 KB |
Output is correct |
26 |
Correct |
2 ms |
460 KB |
Output is correct |
27 |
Correct |
1 ms |
460 KB |
Output is correct |
28 |
Correct |
2 ms |
460 KB |
Output is correct |
29 |
Correct |
2 ms |
460 KB |
Output is correct |
30 |
Correct |
1 ms |
460 KB |
Output is correct |
31 |
Correct |
83 ms |
16716 KB |
Output is correct |
32 |
Correct |
92 ms |
16652 KB |
Output is correct |
33 |
Correct |
86 ms |
16700 KB |
Output is correct |
34 |
Correct |
82 ms |
16664 KB |
Output is correct |
35 |
Correct |
82 ms |
16716 KB |
Output is correct |
36 |
Correct |
81 ms |
16716 KB |
Output is correct |
37 |
Correct |
83 ms |
16648 KB |
Output is correct |
38 |
Correct |
81 ms |
16724 KB |
Output is correct |
39 |
Correct |
9 ms |
16716 KB |
Output is correct |
40 |
Correct |
81 ms |
16728 KB |
Output is correct |
41 |
Correct |
81 ms |
16728 KB |
Output is correct |
42 |
Correct |
101 ms |
16716 KB |
Output is correct |
43 |
Correct |
82 ms |
16728 KB |
Output is correct |
44 |
Correct |
81 ms |
16720 KB |
Output is correct |
45 |
Correct |
9 ms |
16716 KB |
Output is correct |
46 |
Correct |
94 ms |
16664 KB |
Output is correct |
47 |
Correct |
81 ms |
16648 KB |
Output is correct |
48 |
Correct |
9 ms |
16716 KB |
Output is correct |
49 |
Correct |
83 ms |
16716 KB |
Output is correct |
50 |
Correct |
95 ms |
16716 KB |
Output is correct |
51 |
Correct |
82 ms |
16716 KB |
Output is correct |
52 |
Correct |
85 ms |
16716 KB |
Output is correct |
53 |
Correct |
107 ms |
16692 KB |
Output is correct |
54 |
Correct |
106 ms |
16716 KB |
Output is correct |
55 |
Correct |
93 ms |
16716 KB |
Output is correct |
56 |
Correct |
92 ms |
16716 KB |
Output is correct |
57 |
Correct |
92 ms |
16716 KB |
Output is correct |
58 |
Correct |
91 ms |
16716 KB |
Output is correct |