Submission #1340786

#TimeUsernameProblemLanguageResultExecution timeMemory
1340786cubiuterBank (IZhO14_bank)C++20
0 / 100
0 ms348 KiB
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target("avx,avx2,fma")
#define f first
#define s second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using ld = long double;
using ull = unsigned long long;

template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string& s) {
  return '"' + s + '"';
}
string to_string(const char* s) {
  return to_string((string) s);
}
string to_string(bool b) {
  return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << " " << to_string(H);
  debug_out(T...);
}

#define LOCAL
#ifdef LOCAL
#define debug(...) cout << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 123
#endif

const ll inf=1e14+5, mod=998244353, MOD=1e9+7;
const ll INF=1e18;
const int maxn=2e5+123;

const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};

void solve(){
	int n, m; cin>>n>>m;
	vi a(n), b(m);
	for(int i=1; i<=n; i++){
		cin>>a[i-1];
	}
	for(int i=1; i<=m; i++){
		cin>>b[i-1];
	}
	
	vector<pii> dp(1<<m, {0, 0});
	
	dp[0]={0, a[0]};
	
	bool ok=0;
	
	for(int mask=0; mask<(1<<m); mask++){
		for(int last=0; last<m; last++){
			if(mask>>last&1 or dp[mask].s<b[last]){
				continue;
			}
			pii &cur=dp[mask|(1<<last)];
			if(dp[mask].s-b[last]==0){
				if(dp[mask].f==n-1){
					ok=1;
					break;
				}
				cur={dp[mask].f+1, a[dp[mask].f+1]};
			}else{
				cur={dp[mask].f, dp[mask].s-b[last]};
			}
		}
		if(ok){
			break;
		}
	}
	
	if(ok){
		cout<<"YES";
	}else{
		cout<<"NO";
	}
}

int main(){
	freopen("bank.in", "r", stdin);
	freopen("bank.out", "w", stdout);
    //ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int ttt=1; //cin>>ttt;
    while(ttt--){
    	solve();
//    	cout<<"\n";
//    	cout<<string(15, '-')<<"\n";
	}
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen("bank.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen("bank.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...