제출 #1151149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151149		danglayloi1	Bank (IZhO14_bank)	C++20	100 / 100	595 ms	105100 KiB

bank

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=(1<<20)+5;
int n, m, a[nx], b[nx], sum[nx];
bitset<nx> dp[21], cnt;
vector<int> bit[nx];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        cin>>a[i], a[i]+=a[i-1];
    for(int i = 0; i < m; i++)
        cin>>b[i];
    for(int mask = 0; mask < (1<<m); mask++)
    {
        sum[mask]=0;
        for(int i = 0; i < m; i++)
            if(mask>>i&1) sum[mask]+=b[i], bit[mask].emplace_back(i);
    }
    for(int i = 1; i <= n; i++)
    {
        cnt.reset();
        if(i==1) cnt.set();
        else
        {
            for(int mask = 0; mask < (1<<m); mask++)
            {
                if(dp[i-1][mask])
                {
                    cnt[mask]=1;
                    continue;
                }
                for(int j:bit[mask])
                    cnt[mask]=cnt[mask]|cnt[mask^(1<<j)];
            }
        }
        for(int mask = 0; mask < (1<<m); mask++)
            if(sum[mask]==a[i]) dp[i][mask]=cnt[mask];
    }
    if(dp[n].count()>0) cout<<"YES";
    else cout<<"NO";
}

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