Submission #632605

#	Time	Username	Problem	Language	Result	Execution time	Memory
632605		Deep_20	Bank (IZhO14_bank)	C++14	100 / 100	227 ms	8532 KiB

bank

/*/ Author: Deep_20 /*/
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace std;
using namespace __gnu_pbds;
#define _   "\n"
#define F   first
#define S   second
#define pb  push_back
#define pf  push_front
#define int long long int
#define mod 1000000007
#define INF 0x3f3f3f3f3f3f3f3f
#define all(v)  v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ordered_set tree<int, null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

vector<int> dp;
vector<int> a , b;
int n , m;

int solve(int i , int mask , int salary)
{
      if (i == n) return 1;
      if (dp[mask] != -1) return dp[mask];
      int ans = 0;
      for (int j = 0; j < m; ++j)
      {
            if (mask >> j & 1)
            {
                  if (b[j] <= salary)
                  {
                        if (salary - b[j] == 0)
                        {
                              ans |= solve(i + 1 , mask ^ (1 << j) , a[i + 1]);
                        }
                        else
                        {
                              ans |= solve(i , mask ^ (1 << j) , salary - b[j]);
                        }
                  }
            }
      }
      return dp[mask] = ans;
}

void mkc()
{
      cin >> n >> m;
      a.resize(n + 1 , 0);
      b.resize(m);
      for (int i = 0; i < n; ++i)
      {
            cin >> a[i];
      }
      for (int i = 0; i < m; ++i)
      {
            cin >> b[i];
      }
      dp.resize((1 << m) + 1 , -1);
      cout << ((solve(0 , (1 << m) - 1 , a[0])) ? "YES" : "NO");
}

signed main()
{
      ios_base::sync_with_stdio(false);
      cout.tie(0); cin.tie(0);
      mkc();
      return 0;
}

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