Submission #978040

#TimeUsernameProblemLanguageResultExecution timeMemory
978040BentoOreoBank (IZhO14_bank)C++14
71 / 100
1000 ms41304 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<long long, long long>; const ll INF = numeric_limits<ll>::max(); const int inf = numeric_limits<int>::max(); const char nl = '\n', sp = ' '; ll cantor_hash(ll x, ll y){ return (((x + y) * (x + y + 1)) >> 1) + y; } unordered_map<ll, vector<ll> > ks; // void get_key_signature(ll orig, ll curr, int mask, int id,vector<ll> &billz){ // if(curr == 0){ // ks[orig].push_back(mask); // return; // } // if(id == billz.size()){ // return; // } // if(curr - billz[id] >= 0){ // get_key_signature(orig, curr - billz[id], mask + (1 << id), id + 1, billz); // get_key_signature(orig, curr, mask, id + 1, billz); // } // } unordered_map<ll, bool> vis; bool pathexists(int node, int mask,vector<ll> &salary, vector<ll> &billz){ if(node == salary.size()){ return true; } else { if(vis.count(cantor_hash(node,mask))){ return vis[cantor_hash(node,mask)]; } bool flag = false; for(int kbitmask: ks[salary[node]]){ if((mask & kbitmask) == kbitmask){ flag = flag | pathexists(node + 1, mask ^ kbitmask,salary, billz); } } vis[cantor_hash(node,mask)] = flag; return flag; } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<ll> salary; vector<ll> billz; unordered_set<ll> sinit; ll num; for(int i = 0; i < N; i++){ cin >> num; ks[num] = vector<ll>(); salary.push_back(num); sinit.insert(num); } ll totalbillz = 0; for(int i = 0; i < M; i++){ cin >> num; totalbillz += num; billz.push_back(num); } sort(billz.begin(),billz.end()); // sort(billz.begin(),billz.end()); for(int m = 0; m < (1 << M) - 1; m++){ ll temp_t = 0; int maskcopy = m; while(maskcopy){ int ls = maskcopy & -maskcopy; int u = __builtin_ctz(ls); temp_t += billz[u]; maskcopy -= ls; } if(sinit.count(temp_t)){ ks[temp_t].push_back(m); } } // for(ll elem: salary){ // get_key_signature(elem,elem,0,0,billz); // } bool ans = pathexists(0,(1 << M) - 1, salary, billz); if(ans) { cout << "YES" << nl; } else { cout << "NO" << nl; } }

Compilation message (stderr)

bank.cpp: In function 'bool pathexists(int, int, std::vector<long long int>&, std::vector<long long int>&)':
bank.cpp:31:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     if(node == salary.size()){
      |        ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...