Submission #570382

#	Time	Username	Problem	Language	Result	Execution time	Memory
570382		Huy	Bank (IZhO14_bank)	C++17	100 / 100	603 ms	8652 KiB

bank

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;
using ll = long long;
using ldb = long double;
const int N = (int)1e8;
const int maxN = (int)3e5 + 1;
const int mod = 998244353;

void InputFile()
{
    //freopen("scrivener.inp","r",stdin);
    //freopen("scrivener.out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int n,m;
int a[maxN];
int b[maxN];
int dp[(1 << 21)];

void Read()
{
    cin >> n >> m;
    for(int i = 0;i < n;i++)
        cin >> a[i];
    for(int i = 0;i < m;i++)
        cin >> b[i];
}

void Solve()
{
    for(int i = 0;i < (1 << m);i++)
    {
        dp[i] = -1;
    }
    dp[0] = 0;
    for(int i = 0;i < n;i++)
    {
        for(int mask = 0;mask < (1 << m);mask++)
        {
            if(dp[mask] != -1)
            {
                for(int j = 0;j < m;j++)
                {
                    if(!(mask & (1 << j)))
                    {
                        dp[mask | (1 << j)] = dp[mask] + b[j];
                    }
                }
            }
        }
        for(int mask = 0;mask < (1 << m);mask++)
        {
            if(dp[mask] == a[i])
            {
                dp[mask] = 0;
            }
            else dp[mask] = -1;
        }
    }
    for(int mask = 0;mask < (1 << m);mask++)
    {
        if(dp[mask] == 0)
        {
            cout <<"YES";
            return;
        }
    }
    cout <<"NO";
}

void Debug()
{
    //Main_sub();
    //Naive();
}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
    //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

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