제출 #1164403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164403		ivaziva	은행 (IZhO14_bank)	C++17	19 / 100	4 ms	5448 KiB

bank

#include <bits/stdc++.h>

using namespace std;

#define MAXN 20

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

int 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;
}

• Subtask 1: 19 / 19
• Subtask 2: 0 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29