Submission #562714

#	Time	Username	Problem	Language	Result	Execution time	Memory
562714		Bobonbush	Bank (IZhO14_bank)	C++17	100 / 100	255 ms	82608 KiB

bank

#include <bits/stdc++.h>
#define foreach for
#define in :
using namespace std;
typedef long long ll;

/*
Konichiwa
Konichiwa
Ara ~~ ara

Bob no taisuki - Shinobu Kocho
    * * * * *
  *          *
 *         *
*         *        I love SHINOBU <3 <3 <3
 *         *
  *          *
    * * * * *
*/

/*
_________________________


    Author : Bob15324

_________________________
*/

template<class X , class Y>
    bool Minimize(X & x , Y y)
    {
        if(x == -1 || x >y)
        {
            x = y;
            return true;
        }
        return false;
    }

template<class X , class Y>
    bool Maximize(X & x , Y y)
    {
        if( x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

/* End of templates. Let's see what do we have here */
const int N = 20;
int a[N];
int b[N];
int n , m;
int cnt[1001] , dict[1001];
vector<int>List[21];
int dp[N][1 << N];

int DP(int i , int mask )
{

    if(i == n)
    {
        throw 1;
    }
    if(mask == (1 << m)-1)
    {
        return 0;
    }
    if(dp[i][mask] != -1)
    {
        return dp[i][mask];
    }
    dp[i][mask] = 0;
    foreach(int x in List[dict[a[i]]] )
    {
        if(mask & (x))
        {
            continue;
        }
        Maximize(dp[i][mask] ,  DP(i+1 , mask |x));
    }

    return dp[i][mask];
}


int main()
{
    ios_base :: sync_with_stdio(0);cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n ; i++)
    {
        cin >> a[i-1];
        cnt[a[i-1]]++;
    }
    for(int i = 1; i <= m ; i++)
    {
        cin >> b[i-1];
    }
    int dem = 0;
    for(int mask = 1 ; mask <= (1 << m)-1 ; mask++ )
    {
        int sum = 0;
        for(int i = 0 ; i < m ; i++)
        {
            if(mask & (1 << i))
            {
                sum += b[i];
            }
        }
        if(sum <= 1000 && cnt[sum])
        {
            if(dict[sum] == 0)
            {
                dict[sum] = ++dem;
            }
            List[dict[sum]].push_back(mask);
        }
    }

    memset(dp , -1 , sizeof(dp));
    try
    {
        DP(0 , 0);
    }catch(int)
    {
        cout << "YES" <<'\n';
        return 0;
    }
    cout << "NO" <<'\n';




    return 0;
}

//Ehem. My code is amazing. Pay me 2$.Thank you.

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