Submission #823836

#	Time	Username	Problem	Language	Result	Execution time	Memory
823836		Devansh_Rai	Bank (IZhO14_bank)	C++17	100 / 100	298 ms	181148 KiB

bank

// UGG JAA PED!!
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define INF 1000000
#define all(x) (x).begin(), (x).end()
#define loop(i, l, n) for (int i = l; i <= n; i++)
#define loop1(i, l, n) for (int i = l; i <= n; i += 2)
#define revloop(i, l, n) for (int i = l; i >= n; i--)
#define revloop1(i, l, n) for (int i = l; i >= n; i -= 2)

const int M = 1e9 + 7;
long long mod(long long x)
{
    return ((x % M + M) % M);
}
long long add(long long a, long long b)
{
    return mod(mod(a) + mod(b));
}
long long mul(long long a, long long b)
{
    return mod(mod(a) * mod(b));
}

int binpow(int a, int b, int m)
{
    a %= m;
    int res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

/*------------*/

int recur(vector<vector<int>>& dp,int a[], int b[],int n,int m, int ind, int mask,int left)
{
    if(ind==n)
    return 1;
    if(mask==0)
    return 0;
    if(dp[ind][mask]!=-1) return dp[ind][mask];

    int ans = 0;
    loop(i,0,m-1)
    {
        int x = 1<<i;
        if((mask&x)==0)
        continue;

        if(left>b[i])
        {
            ans |= recur(dp,a,b,n,m,ind,mask^x,left-b[i]);
        }
        else if(left==b[i])
        {
            if(ind==n-1) return 1;
            ans |= recur(dp,a,b,n,m,ind+1,mask^x,a[ind+1]);
        }
    }
    return dp[ind][mask] = ans;
}

void solve()
{
    int n,m;
    cin>>n>>m;
    int a[n];
    loop(i,0,n-1)
    {
        cin>>a[i];
    }
    int b[m];
    loop(i,0,m-1)
    {
        cin>>b[i];
    }
    int mask = (1<<m)-1;
    vector<vector<int>>dp(n+1,vector<int>(mask+1,-1));
    if(recur(dp,a,b,n,m,0,mask,a[0]))
    cout<<"YES\n";
    else 
    cout<<"NO\n";

}

int32_t main()
{
    // #ifndef ONLINE_JUDGE
    // freopen('input.txt', 'r', stdin);
    // freopen('output.txt', 'w', stdout);
    // #endif

    // ios_base::sync_with_stdio(0);
    // cin.tie(nullptr);

  	solve();
    return 0;
}

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