Submission #909063

#	Time	Username	Problem	Language	Result	Execution time	Memory
909063		omtheprogrammer1	Bank (IZhO14_bank)	C++17	100 / 100	110 ms	19096 KiB

bank

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define mp make_pair
#define pb push_back
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
#define ins insert
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
bool checkbit(int val, int place) {return (val & (1 << place));}
void setbit(int &val, int place) {val |= 1 << place;}
void clearbit(int &val, int place) {val &= !(1 << place);}
#define readgraph(list, edges) for (int i = 0; i < edges; i++) {int a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

ll FIRSTTRUE(function<bool(ll)> f, ll lb, ll rb) {
  while (lb < rb) {
    ll mb = (lb + rb) / 2;
    f(mb) ? rb = mb : lb = mb + 1;
  }
  return lb;
}
ll LASTTRUE(function<bool(ll)> f, ll lb, ll rb) {
  while (lb < rb) {
    ll mb = (lb + rb + 1) / 2;
    f(mb) ? lb = mb : rb = mb - 1;
  }
  return lb;
}

template<class A> void read(vector<A>& v);
template<class A, size_t S> void read(array<A, S>& a);
template<class T> void read(T& x) {
  cin >> x;
}
void read(double& d) {
  string t;
  read(t);
  d = stod(t);
}
void read(long double& d) {
  string t;
  read(t);
  d = stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
  read(h);
  read(t...);
}
template<class A> void read(vector<A>& x) {
  EACH(a, x)
  read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
  EACH(a, x)
  read(a);
}

string to_string(char c) {
  return string(1, c);
}
string to_string(bool b) {
  return b ? "true" : "false";
}
string to_string(const char* s) {
  return string(s);
}
string to_string(string s) {
  return s;
}
string to_string(vector<bool> v) {
  string res;
  FOR(sz(v))
  res += char('0' + v[i]);
  return res;
}

template<size_t S> string to_string(bitset<S> b) {
  string res;
  FOR(S)
  res += char('0' + b[i]);
  return res;
}
template<class T> string to_string(T v) {
  bool f = 1;
  string res;
  EACH(x, v) {
    if (!f)
      res += ' ';
    f = 0;
    res += to_string(x);
  }
  return res;
}

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
  cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
void EDBG(string names) { names = names; }
template<class H, class... T> void EDBG(string names, H h, T... t) {
  auto pos = names.find(',');
  auto first_name = names.substr(0, pos);
  auto rest = names.substr(pos + 1);
  while (rest.front() == ' ') {
    rest = rest.substr(1);
  }
  cerr << "[" << first_name << "]: [" << to_string(h) << "]" << endl;
  EDBG(rest, t...);
}

// DEBUG
#ifdef LOCAL // compile with -DLOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define edebug(...) EDBG(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 0
#define edebug(...) 0
#endif

mt19937 mt_rng(chrono::steady_clock::now().time_since_epoch().count());
ll randint(ll a, ll b) {
  return uniform_int_distribution<ll>(a, b)(mt_rng);
}
/*--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/

const lld pi = 3.14159265358979323846;
const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;
const ll INF = 1e18;
const int d4i[4] = { -1, 0, 1, 0}, d4j[4] = {0, 1, 0, -1};
const int d8i[8] = { -1, -1, 0, 1, 1, 1, 0, -1}, d8j[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int kni[8] = { +2, +2, -2, -2, 1, -1, 1, -1}, knj[8] = {1, -1, 1, -1, 2, 2, -2, -2};

ll n, m, k, q, l, r, x, y, z , h;
const ll tas = 2e5 + 10;
ll a[tas];
ll b[tas];
pii dp[(1ll << 20)];
string s, t;
// vector<int> grid[tas];
// vector<pii> edges[tas];
ll ans = 0;



void solve(int tc = 0) {

  cin >> n >> m;
  FOR(n) cin >> a[i];
  FOR(m) cin >> b[i];
  ans = 0;
  FOR((1 << m)) dp[i] = { -1e16, 0};
  dp[0] = {0, 0};
  FOR(i, 1, (1ll << m)) {
    FOR(j, 0, m) if (i & (1ll << j)) {
      if (dp[i ^ (1ll << j)].f < -1e14) continue;
      pii cur = dp[i ^ (1ll << j)];
      cur.s += b[j];
      if (cur.s < a[cur.f]) dp[i] = cur;
      else if (cur.s == a[cur.f]) dp[i].f = cur.f + 1, dp[i].s = 0;
    }
    if (dp[i].f == n) ans = 1;
  }
  if (ans) cout << "YES" << endl;
  else cout << "NO" << endl;


}

int main() {
  fastio

#ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  freopen("error.txt", "w", stderr);
#endif

  ll tc = 1;
  // cin >> tc;
  for (int t = 0; t < tc; t++) solve(t);
}

Compilation message (stderr)

bank.cpp: In function 'void clearbit(int&, int)':
bank.cpp:17:48: warning: '<<' in boolean context, did you mean '<'? [-Wint-in-bool-context]
   17 | void clearbit(int &val, int place) {val &= !(1 << place);}
      |                                             ~~~^~~~~~~~~

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