#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,f[1009],g[1009],P[(1<<22)],jm[(1<<22)],s[1009];
bool dp[(1<<22)];
pair <int, int> p[(1<<22)];
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>b;
for(i=0; i<a; i++) cin>>f[i];
for(i=0; i<b; i++) cin>>g[i];
s[0]=f[0];
for(i=1; i<a; i++) s[i]=s[i-1]+f[i];
for(i=0; i<(1<<b); i++){
p[i].first=__builtin_popcount(i);
for(j=0; j<b; j++){
if(((1<<j)&i)!=0){
jm[i]+=g[j];
}
}
e=0;
P[i]=a-1;
for(j=0; j<a; j++){
e+=f[j];
if(e>jm[i]){
P[i]=j-1;
break;
}
}
p[i].second=i;
}
sort(p,p+(1<<b));
dp[0]=1;
P[0]=-1;
for(i=1; i<(1<<b); i++){
for(j=0; j<b; j++){
if(((1<<j)&p[i].second)!=0&&dp[p[i].second-(1<<j)]==1){
if(P[p[i].second-(1<<j)]==P[p[i].second]){
dp[p[i].second]=1;
}else{
if(jm[p[i].second]==s[P[p[i].second]]&&P[p[i].second-(1<<j)]+1==P[p[i].second]) dp[p[i].second]=1;
}
}
}
}
// cout<<dp[(1<<0)]<<endl;
e=0;
for(i=0; i<b; i++){
e+=g[i];
}
if(e<s[a-1]){
cout<<"NO";
}else{
if(dp[(1<<b)-1]==1){
cout<<"YES";
}else{
cout<<"NO";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
11 ms |
1016 KB |
Output is correct |
| 5 |
Correct |
300 ms |
16984 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
3 ms |
376 KB |
Output is correct |
| 8 |
Correct |
328 ms |
17912 KB |
Output is correct |
| 9 |
Correct |
304 ms |
18040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
632 KB |
Output is correct |
| 2 |
Correct |
6 ms |
632 KB |
Output is correct |
| 3 |
Correct |
6 ms |
632 KB |
Output is correct |
| 4 |
Correct |
6 ms |
604 KB |
Output is correct |
| 5 |
Correct |
6 ms |
632 KB |
Output is correct |
| 6 |
Correct |
6 ms |
632 KB |
Output is correct |
| 7 |
Correct |
6 ms |
632 KB |
Output is correct |
| 8 |
Correct |
6 ms |
632 KB |
Output is correct |
| 9 |
Correct |
6 ms |
632 KB |
Output is correct |
| 10 |
Correct |
6 ms |
636 KB |
Output is correct |
| 11 |
Correct |
6 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
11 ms |
1016 KB |
Output is correct |
| 5 |
Correct |
300 ms |
16984 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
3 ms |
376 KB |
Output is correct |
| 8 |
Correct |
328 ms |
17912 KB |
Output is correct |
| 9 |
Correct |
304 ms |
18040 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
6 ms |
632 KB |
Output is correct |
| 21 |
Correct |
6 ms |
632 KB |
Output is correct |
| 22 |
Correct |
6 ms |
632 KB |
Output is correct |
| 23 |
Correct |
6 ms |
604 KB |
Output is correct |
| 24 |
Correct |
6 ms |
632 KB |
Output is correct |
| 25 |
Correct |
6 ms |
632 KB |
Output is correct |
| 26 |
Correct |
6 ms |
632 KB |
Output is correct |
| 27 |
Correct |
6 ms |
632 KB |
Output is correct |
| 28 |
Correct |
6 ms |
632 KB |
Output is correct |
| 29 |
Correct |
6 ms |
636 KB |
Output is correct |
| 30 |
Correct |
6 ms |
632 KB |
Output is correct |
| 31 |
Correct |
327 ms |
17860 KB |
Output is correct |
| 32 |
Correct |
329 ms |
17920 KB |
Output is correct |
| 33 |
Correct |
315 ms |
17980 KB |
Output is correct |
| 34 |
Correct |
299 ms |
17400 KB |
Output is correct |
| 35 |
Correct |
321 ms |
17656 KB |
Output is correct |
| 36 |
Correct |
305 ms |
17016 KB |
Output is correct |
| 37 |
Correct |
297 ms |
17016 KB |
Output is correct |
| 38 |
Correct |
299 ms |
16964 KB |
Output is correct |
| 39 |
Correct |
307 ms |
17912 KB |
Output is correct |
| 40 |
Correct |
301 ms |
16888 KB |
Output is correct |
| 41 |
Correct |
309 ms |
16992 KB |
Output is correct |
| 42 |
Correct |
354 ms |
17912 KB |
Output is correct |
| 43 |
Correct |
305 ms |
17784 KB |
Output is correct |
| 44 |
Correct |
301 ms |
16888 KB |
Output is correct |
| 45 |
Correct |
356 ms |
17780 KB |
Output is correct |
| 46 |
Correct |
334 ms |
17944 KB |
Output is correct |
| 47 |
Correct |
302 ms |
17016 KB |
Output is correct |
| 48 |
Correct |
325 ms |
17916 KB |
Output is correct |
| 49 |
Correct |
296 ms |
17016 KB |
Output is correct |
| 50 |
Correct |
320 ms |
17784 KB |
Output is correct |
| 51 |
Correct |
316 ms |
16988 KB |
Output is correct |
| 52 |
Correct |
304 ms |
17784 KB |
Output is correct |
| 53 |
Correct |
323 ms |
17784 KB |
Output is correct |
| 54 |
Correct |
327 ms |
17784 KB |
Output is correct |
| 55 |
Correct |
320 ms |
17816 KB |
Output is correct |
| 56 |
Correct |
323 ms |
17912 KB |
Output is correct |
| 57 |
Correct |
318 ms |
18016 KB |
Output is correct |
| 58 |
Correct |
318 ms |
17788 KB |
Output is correct |
