This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
long long dp[(1<<21)];
long long a[21];
long long b[21];
long long tong[(1<<21)];
long long vt[(1<<21)];
long long thua[(1<<21)];
signed main ()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin >> n >> m;
for (int i=1;i<=n;i++)
{
cin >> a[i];
}
a[n+1]=10000000000;
for (int i=1;i<=m;i++)
{
cin >> b[i];
}
dp[0]=1;
thua[0]=a[1];
vt[0]=1;
for (int i=1;i<=(1<<m);i++)
{
for (int i2=1;i2<=m;i2++)
{
if (!(i&(1<<(i2-1)))) continue;
tong[i]+=b[i2];
}
}
for (int i=1;i<=(1<<m);i++)
{
long long tong2=0;
for (int i2=1;i2<=n+1;i2++)
{
tong2=tong2+a[i2];
if (tong2>tong[i])
{
vt[i]=i2;
thua[i]=tong2-tong[i];
break;
}
}
}
for (int i=1;i<=(1<<m);i++)
{
for (int i2=1;i2<=m;i2++)
{
if (!(i&(1<<(i2-1)))) continue;
int bit=i^(1<<(i2-1));
if (dp[bit]==0) continue;
if (thua[bit]>=b[i2])
{
dp[i]=1;
}
}
}
// cout << vt[9] << " " << thua[9] << " " << tong[9] << " " << dp[9] << '\n';
for (int i=1;i<=(1<<m);i++)
{
if ((dp[i]) and (vt[i]==n+1))
{
// cout << i << '\n';
cout << "YES";
return 0;
}
}
cout << "NO";
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |