Submission #977998

#TimeUsernameProblemLanguageResultExecution timeMemory
977998BentoOreoBank (IZhO14_bank)C++14
52 / 100
1037 ms44740 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){ ll ans = (((x + y) * (x + y + 1)) >> 1) + y; // cout << ans << nl; return ans; } unordered_map<ll,bool> vis; bool f(int id, ll mask, ll val, int M, vector<ll> &salary, vector<ll> &billz ){ // cout << id << sp << mask << sp << val << nl; if(vis.count(cantor_hash(mask,val))){ return vis[cantor_hash(mask,val)]; } else { if(id == salary.size()){ return true; } else if(val == 0){ return f(id + 1,mask,salary[id + 1], M, salary, billz); } else { bool flag = false; for(int i = 0; (i < M) && (val - billz[i] >= 0); i++){ if((mask & (1 << i)) != 0){ flag = flag | f(id, mask ^ (1 << i),val - billz[i],M, salary,billz); // flag = true; } } vis[cantor_hash(mask,val)] = 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; ll num; for(int i = 0; i < N; i++){ cin >> num; salary.push_back(num); } for(int i = 0; i < M; i++){ cin >> num; billz.push_back(num); } sort(billz.begin(),billz.end()); ll mask = (1 << M) - 1; bool ans = f(0,mask,salary[0], M ,salary, billz); if(ans){ cout << "YES" << nl; } else { cout << "NO" << nl; } }

Compilation message (stderr)

bank.cpp: In function 'bool f(int, ll, ll, int, std::vector<long long int>&, std::vector<long long int>&)':
bank.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         if(id == 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...