Submission #817705

#	Time	Username	Problem	Language	Result	Execution time	Memory
817705		darishkhan	Bank (IZhO14_bank)	C++17	100 / 100	116 ms	172772 KiB

bank

//UGG JAA PED
 
 
#include<bits/stdc++.h>
using namespace std;
#define intt int64_t 
 
//const intt mod = 1000000007;
#define fu(i,a,n) for(intt i=a;i<n;i++)       
#define fus(i,a,n, k) for(intt i=a;i<n;i+=k)  
#define fd(i,n,a) for(int i=n-1;i>=a;i--)     
#define fds(i,n,a, k) for(int i=n-1;i>=a;i-=k)
 
intt binpow(intt a, intt b, intt m) {
  a %= m;
  intt res = 1;
  while (b > 0) {
      if (b & 1)
          res = res * a % m;
      a = a * a % m;
      b >>= 1;
  }
  return res;
}
 
bool isPrime(int n)
{
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
bool func(vector<vector<intt>> &dp, intt i, intt left, intt n, intt m,vector<int> &people, vector<int> &notes, intt mask)
{
    if(i==-1) 
    {
        cout<<"okay";
        return true;
    }
    if(mask==0) return false;

    if(dp[i][mask]!=-1) return dp[i][mask];

    bool ans = false;
    for(intt j=0;j<m;j++)
    {
        // cout<<i<<j<<left<<", "<<mask<<" ";
        if((mask & (1<<j)))
        {
            // cout<<i<<" "<<j<<"\n";
            if(notes[j]==left)
            {
                // cout<<"m";
                if(i==0) return dp[i][mask]= 1;
                ans = ans or func(dp, i-1, people[i-1], n, m, people, notes, mask^(1<<j));
            }
            else if(notes[j]<left)
            {
                // cout<<"n";
                ans = ans or func(dp, i, left-notes[j], n, m, people, notes, mask^(1<<j));
            }
        }
        // return dp[i][mask]=ans;
    }
    return dp[i][mask]=ans;
}


 
void solve()
{
    intt n, m;
    cin>>n>>m;
    vector<int> people(n), notes(m);

    fu(i, 0, n) cin>>people[i];
    fu(i, 0, m) cin>>notes[i];

    intt mask = (1<<m)-1;
    vector<vector<intt>> dp(n, vector<intt>(mask+1, -1));
    if(func(dp, n-1, people[n-1], n, m, people, notes, mask)) cout<<"YES\n";
    else cout<<"NO\n";

}
 
int main()
{
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // int t;
    // cin>>t;
    // while(t--)
    // {
        solve();
    // }
    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'bool func(std::vector<std::vector<long int> >&, int64_t, int64_t, int64_t, int64_t, std::vector<int>&, std::vector<int>&, int64_t)':
bank.cpp:63:44: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   63 |                 if(i==0) return dp[i][mask]= 1;
bank.cpp:74:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   74 |     return dp[i][mask]=ans;

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