제출 #970598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
970598		MercubytheFirst	은행 (IZhO14_bank)	C++17	100 / 100	100 ms	16984 KiB

bank

#include "bits/stdc++.h"
#define pb push_back
#define endl '\n'
#define fi first
#define se second
#define CDIV(a,b) (((a)+(b)-(1))/(b))
using ll = long long;
using ld = long double;
const ll inf = 1e15 + 37;
const ll mod = 1e9 + 7;
const ll N = 3e5 + 37;
const ld eps = 1e-9;
const ld PI = acos((ld)-1);
 

template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s);
template<typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v);
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


inline void solve(){
  ll n, m;
  cin >> n >> m;
  vector<ll> ppl(n), notes(m);
  cin >> ppl >> notes;
  const ll SZ = 1 << m;
  vector<pair<ll, ll> > dp(SZ, {-1, -inf});
  dp[0] = {0, 0};
  bool ok = false;
  for(ll mask = 1; mask < SZ; ++mask) {
    for(ll i = 0; i < m; ++i) {
      if(!(1 << i & mask))
        continue;
      const ll prev_mask = mask ^ (1 << i);
      const auto [cur_person, collected] = dp[prev_mask];
      if(cur_person >= n) {
        ok = true;
        break;
      }
      if(cur_person == -1)
        continue;
      if(collected + notes[i] == ppl[cur_person]) {
        dp[mask] = max(dp[mask], make_pair(cur_person + 1, 0LL));
      }
      else if(collected + notes[i] < ppl[cur_person]) {
        dp[mask] = max(dp[mask], make_pair(cur_person, collected + notes[i]));
      }
    }
    if(ok)
      break;
  }
  // for(ll i = 0; i < SZ; ++i) {
  //   string s = bitset<5>(i).to_string();
  //   reverse(s.begin(), s.end());
  //   cout << s << " : " << dp[i] << endl;
  // }
  cout << (max_element(dp.begin(), dp.end())->first >= n ? "YES" : "NO");
  
}


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

template<typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
  for(T& x : v)
    is >> x;
  return is;
}

template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
  os << "[";
  for(size_t i = 0; i + 1 < N; ++i) {
    os << a[i] << ", ";
  }
  if(N > 0)
    os << a[N - 1];
  os << "]";
  return os;
}

template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
  os << "(" << p.first << ", " << p.second << ") ";
  return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << '[';
  for(auto x : v)
    os << x << ", ";
  os << "] ";
  return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}
//
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}

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