제출 #1355368

#제출 시각아이디문제언어결과실행 시간메모리
1355368t^t...은행 (IZhO14_bank)C++20
100 / 100
84 ms8540 KiB
/*=======================================
  Build    : LOCAL / Debug
  Compiler : g++ -std=gnu++17
  Note: read problem twice ฅ(^>⩊<^) ฅ
=======================================*/
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
  #define _GLIBCXX_DEBUG
  #include "debug.hpp"
#else
  #define debug(...) ((void)0)
#endif

#define sz(v) ((int)((v).size()))
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

using ll = int64_t;
using db = long double;

const int mxN = (int)2e5+5;
const int xdir[4]{1,0,-1,0}, ydir[4]{0,1,0,-1};
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<typename T> int lwb(const vector<T>& a, const T& x){
  return lower_bound(a.begin(), a.end(), x) - a.begin(); }
template<typename T> int upb(const vector<T>& a, const T& x){
  return upper_bound(a.begin(), a.end(), x) - a.begin(); }

constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int ctz(int x) {  // assert(x >= 0); 
  return x == 0 ? -1 : __builtin_ctz(x); } // # of trailing zeros
constexpr int bits(int x) { // assert(x >= 0); 
  return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x)) 
  
template<typename T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } 
template<typename T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

template<typename T, typename V>
void init_vector(T& v, const std::vector<int>& /*dims*/, const V& val, int /*idx*/) { v = val; }

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  vector<int> b(m);
  for(auto& x: a) cin >> x;
  for(auto& x: b) cin >> x;

  vector<pair<int,int>> dp(1<<m, make_pair(INT_MAX, 0));   
  dp[0] = {0, 0};
  for(int s = 1; s < 1<<m; ++s) 
    for(int i = 0; i < m; ++i) 
      if(s&(1<<i)) {
        int ps = s^(1<<i);
        auto [r, nxt] = dp[ps];
        nxt = -nxt;
        if(nxt < n && r + b[i] == a[nxt]) {
          r = 0;
          nxt++;
        } else {
          r += b[i]; 
        }
        ckmin(dp[s], make_pair(r, -nxt)); 
      }

  cout << (n == -dp[(1<<m)-1].second ? "YES":"NO") << '\n';
  return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…