제출 #817703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817703		darishkhan	은행 (IZhO14_bank)	C++17	0 / 100	111 ms	262144 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 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 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;
}

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