이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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... |