Submission #1122575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122575		barkolorious	Bank (IZhO14_bank)	C++17	0 / 100	1100 ms	90344 KiB

bank

// barkolorious - 29 November 2024
// in god, do we trust? 
#include <bits/stdc++.h>
using namespace std;

#define FIN(x) freopen(x ".in", "r", stdin)
#define FOUT(x) freopen(x ".out", "w", stdout)
#define int long long
#define pb  push_back
#define fr  first
#define sc  second
#define __  << " " << 
#define check_bit(a, i) (((a) & (1 << (i))) >> (i))
#define flip_bit(a, i)  ((a) & ~(1 << (i)))

const int N = 2e5 + 5;

void solve () {
  int n, m; cin >> n >> m;

  vector<int> a(n), b(m);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) cin >> b[i];

  int E = (1 << m);
  pair<int, int> dp[E];
  dp[0] = {0, 0};
  for (int s = 0; s < E; s++) {
    if (!s) dp[s] = {-1, -1};
    for (int i = 0; i < m; i++) {
      if (!check_bit(s, i)) continue;
      
      auto last = dp[flip_bit(s, i)];
      if (last.fr == -1) continue;

      if (last.sc + b[i] == a[last.fr]) { 
        dp[s] = {last.fr + 1, 0};
      } else if (last.sc + b[i] < a[last.fr]) { 
        dp[s] = {last.fr, last.sc + b[i]}; 
      }
    }
    if (dp[s].fr == n) {
      cout << "YES" << endl;
      return;
    }
  }
  cout << "NO" << endl;
}

/*
-- Sample 1 --
Input:
1 5
8
4 2 5 1 3
Output:
YES

-- Sample 2 --
Input:
2 6
9 10
5 4 8 6 3 11
Output:
NO
*/

/*
g++ -std=c++17 -O2 -Wall -DLOCAL "C:\Users\LENOVO\Desktop\BARKIN\Genel\Programming\Competitive\Questions\oj.uz\IZhO14\IZhO14_bank.cpp" -o _run
*/

int32_t main () {
  #ifndef LOCAL
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
  #endif

  #ifdef LOCAL
    clock_t __START__ = clock();
    FILE* __FILE_IN__ = FIN("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
    FILE* __FILE_OUT__ = FOUT("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
  #else
    #ifndef ONLINE_JUDGE
      FILE* __FILE_IN__ = FIN("usaco");
      FILE* __FILE_OUT__ = FOUT("usaco");
    #endif
  #endif

  solve();

  #ifdef LOCAL
    fclose(__FILE_IN__);
    fclose(__FILE_OUT__);
    cerr << "Executed in: " << fixed << setprecision(3) << (double) (clock() - __START__) / CLOCKS_PER_SEC << "seconds" << endl;
  #else
    #ifndef ONLINE_JUDGE
      fclose(__FILE_IN__);
      fclose(__FILE_OUT__);
    #endif
  #endif

  return 0;
}

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