# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
765606 |
2023-06-24T22:14:28 Z |
HD1 |
Bank (IZhO14_bank) |
C++14 |
|
238 ms |
173120 KB |
//we are all lost trying to be someone.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define sz(x) ll(x.size())
#define reve(x) reverse(x.begin(),x.end())
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
const ll MAX=1e5+10;
const ll mod=1e9+7;
const ll inf=1e18+7;
vector<ll>s;
ll A[1010],B[1010];
map<ll,vector<ll>> masks;
map<ll,vector<ll>> c;
ll dp[21][(1<<20)+1000];
ll n, m;
void prin(ll x){
for(ll i=m-1; i>=0; i--){
cout<<((x>>i)&1);
}
cout<<endl;
return;
}
bool DP(ll i, ll mask){
if(i<0 or mask==0)return 1;
if(dp[i][mask]!=-1)return dp[i][mask];
dp[i][mask]=0;
for(ll x: masks[s[i]]){
if((mask&x)==x){
if(i==0)dp[i][mask]=1;
dp[i][mask]=dp[i][mask] or DP(i-1,mask^x);
}
}
return dp[i][mask];
}
void solve(){
cin>>n>>m;
memset(dp, -1, sizeof dp);
for(ll i=0; i<n; i++){
ll a;
cin>>a;
s.push_back(a);
c[a].push_back(i);
}
for(ll i=0; i<m; i++){
cin>>B[i];
}
sort(s.begin(),s.end());
for(ll mask=0; mask<(1<<m); mask++){
ll sum=0;
for(ll j=0; j<m; j++){
if((mask>>j)&1){
sum+=B[j];
}
}
ll pos=lower_bound(s.begin(),s.end(),sum)-s.begin();
if(pos<n and s[pos]==sum){
masks[s[pos]].push_back(mask);
for(ll it : c[s[pos]]) dp[it][mask]=1;
}
}
if(DP(n-1,(1<<m)-1)){
cout<<"YES"<<endl;
}
else cout<<"NO"<<endl;
}
int main(){
fastio;
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
172720 KB |
Output is correct |
2 |
Correct |
57 ms |
172740 KB |
Output is correct |
3 |
Correct |
62 ms |
172836 KB |
Output is correct |
4 |
Correct |
60 ms |
172828 KB |
Output is correct |
5 |
Correct |
124 ms |
172752 KB |
Output is correct |
6 |
Correct |
59 ms |
172748 KB |
Output is correct |
7 |
Correct |
70 ms |
172776 KB |
Output is correct |
8 |
Correct |
120 ms |
172952 KB |
Output is correct |
9 |
Correct |
123 ms |
172832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
172768 KB |
Output is correct |
2 |
Correct |
58 ms |
172824 KB |
Output is correct |
3 |
Correct |
59 ms |
172752 KB |
Output is correct |
4 |
Correct |
59 ms |
172776 KB |
Output is correct |
5 |
Correct |
70 ms |
172764 KB |
Output is correct |
6 |
Correct |
62 ms |
172820 KB |
Output is correct |
7 |
Correct |
58 ms |
172728 KB |
Output is correct |
8 |
Correct |
60 ms |
172736 KB |
Output is correct |
9 |
Correct |
60 ms |
172812 KB |
Output is correct |
10 |
Correct |
60 ms |
172748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
172836 KB |
Output is correct |
2 |
Correct |
61 ms |
172820 KB |
Output is correct |
3 |
Correct |
70 ms |
172792 KB |
Output is correct |
4 |
Correct |
60 ms |
172760 KB |
Output is correct |
5 |
Correct |
59 ms |
172764 KB |
Output is correct |
6 |
Correct |
62 ms |
172748 KB |
Output is correct |
7 |
Correct |
60 ms |
172780 KB |
Output is correct |
8 |
Correct |
62 ms |
172812 KB |
Output is correct |
9 |
Correct |
60 ms |
172824 KB |
Output is correct |
10 |
Correct |
60 ms |
172892 KB |
Output is correct |
11 |
Correct |
58 ms |
172780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
172720 KB |
Output is correct |
2 |
Correct |
57 ms |
172740 KB |
Output is correct |
3 |
Correct |
62 ms |
172836 KB |
Output is correct |
4 |
Correct |
60 ms |
172828 KB |
Output is correct |
5 |
Correct |
124 ms |
172752 KB |
Output is correct |
6 |
Correct |
59 ms |
172748 KB |
Output is correct |
7 |
Correct |
70 ms |
172776 KB |
Output is correct |
8 |
Correct |
120 ms |
172952 KB |
Output is correct |
9 |
Correct |
123 ms |
172832 KB |
Output is correct |
10 |
Correct |
58 ms |
172768 KB |
Output is correct |
11 |
Correct |
58 ms |
172824 KB |
Output is correct |
12 |
Correct |
59 ms |
172752 KB |
Output is correct |
13 |
Correct |
59 ms |
172776 KB |
Output is correct |
14 |
Correct |
70 ms |
172764 KB |
Output is correct |
15 |
Correct |
62 ms |
172820 KB |
Output is correct |
16 |
Correct |
58 ms |
172728 KB |
Output is correct |
17 |
Correct |
60 ms |
172736 KB |
Output is correct |
18 |
Correct |
60 ms |
172812 KB |
Output is correct |
19 |
Correct |
60 ms |
172748 KB |
Output is correct |
20 |
Correct |
61 ms |
172836 KB |
Output is correct |
21 |
Correct |
61 ms |
172820 KB |
Output is correct |
22 |
Correct |
70 ms |
172792 KB |
Output is correct |
23 |
Correct |
60 ms |
172760 KB |
Output is correct |
24 |
Correct |
59 ms |
172764 KB |
Output is correct |
25 |
Correct |
62 ms |
172748 KB |
Output is correct |
26 |
Correct |
60 ms |
172780 KB |
Output is correct |
27 |
Correct |
62 ms |
172812 KB |
Output is correct |
28 |
Correct |
60 ms |
172824 KB |
Output is correct |
29 |
Correct |
60 ms |
172892 KB |
Output is correct |
30 |
Correct |
58 ms |
172780 KB |
Output is correct |
31 |
Correct |
121 ms |
172836 KB |
Output is correct |
32 |
Correct |
122 ms |
173120 KB |
Output is correct |
33 |
Correct |
127 ms |
172752 KB |
Output is correct |
34 |
Correct |
128 ms |
172760 KB |
Output is correct |
35 |
Correct |
128 ms |
172760 KB |
Output is correct |
36 |
Correct |
138 ms |
172836 KB |
Output is correct |
37 |
Correct |
125 ms |
172832 KB |
Output is correct |
38 |
Correct |
130 ms |
172832 KB |
Output is correct |
39 |
Correct |
130 ms |
172764 KB |
Output is correct |
40 |
Correct |
128 ms |
172784 KB |
Output is correct |
41 |
Correct |
129 ms |
172804 KB |
Output is correct |
42 |
Correct |
128 ms |
172876 KB |
Output is correct |
43 |
Correct |
127 ms |
172752 KB |
Output is correct |
44 |
Correct |
132 ms |
172836 KB |
Output is correct |
45 |
Correct |
128 ms |
172856 KB |
Output is correct |
46 |
Correct |
124 ms |
172748 KB |
Output is correct |
47 |
Correct |
131 ms |
172968 KB |
Output is correct |
48 |
Correct |
120 ms |
172896 KB |
Output is correct |
49 |
Correct |
125 ms |
172836 KB |
Output is correct |
50 |
Correct |
138 ms |
172732 KB |
Output is correct |
51 |
Correct |
141 ms |
173028 KB |
Output is correct |
52 |
Correct |
238 ms |
172840 KB |
Output is correct |
53 |
Correct |
126 ms |
172868 KB |
Output is correct |
54 |
Correct |
129 ms |
172940 KB |
Output is correct |
55 |
Correct |
133 ms |
172956 KB |
Output is correct |
56 |
Correct |
127 ms |
172744 KB |
Output is correct |
57 |
Incorrect |
128 ms |
172840 KB |
Output isn't correct |
58 |
Halted |
0 ms |
0 KB |
- |