제출 #1164406

#제출 시각아이디문제언어결과실행 시간메모리
1164406ivaziva은행 (IZhO14_bank)C++17
19 / 100
8 ms10252 KiB
#include <bits/stdc++.h>

using namespace std;

#define MAXN 22
#define int long long

int n,m;
int a[MAXN],b[MAXN],pref[MAXN];
bool dp[2][1<<MAXN];
int cost[1<<MAXN];
vector<int> maske[2];

int32_t main()
{
    ios_base::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;dp[0][0]=true;pref[0]=0;
    for (int i=0;i<n;i++) {cin>>a[i];pref[i+1]=pref[i]+a[i];}
    for (int i=0;i<m;i++) cin>>b[i];
    cost[0]=0;maske[0].push_back(0);
    for (int maska=1;maska<(1<<m);maska++)
    {
        int lowest=__builtin_ctz(maska);
        cost[maska]=cost[maska^(1<<lowest)]+b[lowest];
        if (cost[maska]==pref[1]) maske[1].push_back(maska);
    }
    for (int i=0;i<n;i++)
    {
        for (int maska:maske[0])
        {
            if (!dp[0][maska]) continue;
            for (int sledmaska:maske[1])
            {
                if ((sledmaska&maska)!=maska) continue;
                int trenmaska=sledmaska^maska;
                if (cost[trenmaska]==a[i]) dp[1][sledmaska]=true;
            }
        }
        if (i==n-1) break;
        for (int maska=0;maska<(1<<m);maska++) {dp[0][maska]=dp[1][maska];dp[1][maska]=false;}
        maske[0].clear();
        for (int maska:maske[1]) maske[0].push_back(maska);
        maske[1].clear();
    }
    for (int maska=0;maska<(1<<m);maska++)
    {
        if (dp[1][maska]) {cout<<"YES"<<endl;return 0;}
    }
    cout<<"NO"<<endl;return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...