Submission #1324900

#TimeUsernameProblemLanguageResultExecution timeMemory
1324900joesephdiverBank (IZhO14_bank)C++20
52 / 100
2 ms568 KiB
#include <bits/stdc++.h>
using namespace std;
 
template<class T> using V = vector<T>;
 
using ll  = long long;
using ull = unsigned long long;
using ld  = long double;
 
using pii = pair<int,int>;
using pll = pair<ll,ll>;
 
using vi = V<int>;
using vll = V<ll>;
using vs = V<string>;
 
#define all(x)  begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x)   (int)((x).size())
 
#define pb  push_back
#define eb  emplace_back
#define mp  make_pair
 
#define rep(i,n)    for (int i = 0; i < (int)(n); ++i)
#define rep1(i,n)   for (int i = 1; i <= (int)(n); ++i)
#define forr(i,a,b) for (int i = (a); i <= (int)(b); ++i)
#define rfor(i,a,b) for (int i = (a); i >= (int)(b); --i)
 
const ll  INF64 = (1LL<<62) - 1;
const int INF   = 0x3f3f3f3f;    
const int MOD   = 1'000'000'007;
 
struct FastIO {
  FastIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.setf(std::ios::fixed); cout.precision(12);
  }
} fastio;
 
inline void setIO(const string& inFile, const string& outFile){
  if (!inFile.empty())  assert(freopen(inFile.c_str(), "r", stdin)  != nullptr);
  if (!outFile.empty()) assert(freopen(outFile.c_str(), "w", stdout) != nullptr);
}
 
inline void setIO(const string& base){
  setIO(base + ".in", base + ".out");
}
 
template <class T, class U>
struct PairHash {
    std::size_t operator()(const std::pair<T, U>& p) const noexcept {
        std::size_t h1 = std::hash<T>{}(p.first);
        std::size_t h2 = std::hash<U>{}(p.second);
        return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
    }
};
 
template<class T> inline bool chmin(T& a, const T& b){ if(b < a){ a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, const T& b){ if(a < b){ a = b; return true; } return false; }
 
template<class T> inline T ceil_div(T a, T b){
  return (a>=0 ? (a + b - 1)/b : a/b);
}
template<class T> inline T floor_div(T a, T b){
  return (a>=0 ? a/b : (a - b + 1)/b);
}
 
template<class T> inline T clampv(T x, T lo, T hi){ return x < lo ? lo : (x > hi ? hi : x); }
 
template<class T> string to_str(const T& x){ std::ostringstream os; os << x; return os.str(); }
 
template<class T>
vector<int> compress(const vector<T>& a, vector<T>* values_out=nullptr){
  vector<T> v = a; sort(all(v)); v.erase(unique(all(v)), v.end());
  if(values_out) *values_out = v;
  vector<int> id(a.size());
  rep(i, a.size()) id[i] = (int)(lower_bound(all(v), a[i]) - v.begin());
  return id;
}
 
template<class T> istream& operator>>(istream& is, vector<T>& v){ for (auto& x : v) is >> x; return is; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& v){
  for (int i = 0; i < sz(v); ++i) os << v[i] << (i+1==sz(v) ? "" : " ");
  return os;
}

template <class T, class... Rest>
auto vec(const T& value, size_t n, Rest... rest) {
    if constexpr (sizeof...(rest) == 0) {
        return vector<T>(n, value);
    } else {
        auto inner = vec<T>(value, (size_t)rest...);
        return vector<decltype(inner)>(n, inner);
    }
}
 
struct DSU {
    V<int> e; void init(int N) { e = V<int>(N,-1); }
    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } 
    bool sameSet(int a, int b) { return get(a) == get(b); }
    int size(int x) { return -e[get(x)]; }
    bool unite(int x, int y) {
        x = get(x), y = get(y); if (x == y) return 0;
        if (e[x] > e[y]) swap(x,y);
        e[x] += e[y]; e[y] = x; return 1;
    }
};
 
const int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};
const int dx8[8] = {1,1,0,-1,-1,-1,0,1}, dy8[8] = {0,1,1,1,0,-1,-1,-1};
const int kx[8]  = {1,2,2,1,-1,-2,-2,-1}, ky[8] = {2,1,-1,-2,-2,-1,1,2};
 
int mod = 1000000007;

template<class Iterator>
bool next_subset(Iterator first, Iterator last, int max_value){
	auto it = prev(last);
	while(*it == max_value){
		*it = 0;
		if(it == first){
			return 0;
		}
		it--;
	}
	(*it)++;
	return 1;
}

struct cow{
	int h, w, s;
};

 
int main(){
	int N, M;
	cin >> N >> M;
	int a[N], b[M];
	rep(i, N) cin >> a[i];
	rep(i, M) cin >> b[i];
	rep1(i, N-1) a[i] += a[i-1]; 
	pii dp[20001]{};
	rep1(s, (1 << M)-1){
		rep(i, M){
			int bit = 1 << i;
			if(s & bit){
				dp[s] = max(dp[s], make_pair(dp[s^bit].first+(dp[s^bit].second+b[i] == a[dp[s^bit].first]), dp[s^bit].second+b[i]));
			}
			if(dp[s].first == N){
				cout << "YES" << endl;
				return 0;
			}
		}
	}
	cout << "NO" << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...