Submission #1205761

#TimeUsernameProblemLanguageResultExecution timeMemory
1205761rkgenaBank (IZhO14_bank)C++20
100 / 100
104 ms16712 KiB
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define IOS ios::sync_with_stdio(0); cin.tie(0); #define lli long long int #define pb push_back #define all(x) x.begin(),x.end() #define rep(i,a,b) for(int i=a;i<=b;i++) #define repp(i,a,b) for(int i=a;i>=b;i--) #define vi vector<lli> #define vvi vector<vi> #define vpi vector<pair<lli,lli>> #define pi pair<lli,lli> #define msi multiset<lli> #define mspi multiset<pair<lli,lli>> #define mii map<lli,lli> #define mpi map<pair<lli,lli>,lli> #define si set<lli> #define spi set<pair<lli,lli>> #define qi queue<lli> #define pqi priority_queue<lli> #define pqimin priority_queue<lli,vi,greater<lli>> #define geti(n) lli n; cin>>n; #define get2i(n,m) lli n,m; cin>>n>>m; #define get3i(n,m,k) lli n,m,k; cin>>n>>m>>k; #define getvi(v,n) vi v(n); for(lli i=0;i<n;i++) cin>>v[i]; #define getvvi(v,n,m) vvi v(n,vi(m)); for(lli i=0;i<n;i++) for(lli j=0;j<m;j++) cin>>v[i][j]; #define getvpi(v,n) vpi v(n); for(lli i=0;i<n;i++) cin>>v[i].first>>v[i].second; #define getpi (p) pi p; cin>>p.first>>p.second; #define getmii(m,n) mii m; for(lli i=0;i<n;i++) { lli a,b; cin>>a>>b; m[a]=b; } #define getstr(s) string s; cin>>s; template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<class T1, class T2> using ordered_map = tree<T1, T2, less<T1>, rb_tree_tag, tree_order_statistics_node_update>; void print(lli n) { cout << n << "\n"; } void print(lli n, lli m) { cout << n << " " << m << "\n"; } void print(lli n, lli m, lli k) { cout << n << " " << m << " " << k << "\n"; } void print(vi v) { for (auto i : v) cout << i << " "; cout << "\n"; } void print(vvi v) { for (auto i : v) { for (auto j : i) cout << j << " "; cout << "\n"; } } void print(string s) { cout << s << "\n"; } const lli MOD = 1e9 + 7; struct mi { int v; explicit operator int() const { return v; } mi() { v = 0; } mi(long long _v) : v(_v % MOD) { v += (v < 0) * MOD; } }; mi &operator+=(mi &a, mi b) { if ((a.v += b.v) >= MOD) a.v -= MOD; return a; } mi &operator-=(mi &a, mi b) { if ((a.v -= b.v) < 0) a.v += MOD; return a; } mi operator+(mi a, mi b) { return a += b; } mi operator-(mi a, mi b) { return a -= b; } mi operator*(mi a, mi b) { return mi((long long)a.v * b.v); } mi &operator*=(mi &a, mi b) { return a = a * b; } mi pow(mi a, long long p) { assert(p >= 0); return p == 0 ? 1 : pow(a * a, p / 2) * (p & 1 ? a : 1); } mi inv(mi a) { assert(a.v != 0); return pow(a, MOD - 2); } mi operator/(mi a, mi b) { return a * inv(b); } vi complete_subset_graphs(vi adj){ // adj[i] = 1 << j if i is connected to j // n<=20 lli n = adj.size(); vi dp(1ll<<n,0); rep(mask,0,(1<<n)-1){ bool complete = true; rep(i,0,n-1){ if((mask & (1ll<<i))){ if(((adj[i] | (1ll<<i))&mask) != mask){ complete = false; break; } } } if(complete) dp[mask] = 1; } return dp; } vi subsets_of_mask(lli mask){ vi subsets; for(lli submask = mask; submask != 0; submask = (submask-1)&mask){ lli subset = mask^submask; // subset is a subset of mask // {submask} = {mask} - {subset} subsets.pb(submask); } return subsets; } vpi prm_fact(lli a) { vpi res; for (lli i = 2; i * i <= a; ++i) { if (a % i == 0) { int cnt = 0; while (a % i == 0) { a /= i; cnt++; } res.pb({i, cnt}); } } if (a > 1) res.pb({a, 1}); return res; } void solve() { lli n,m; cin>>n>>m; vi a(n),b(m); rep(i,0,n-1) cin>>a[i]; rep(i,0,m-1) cin>>b[i]; vi leftover(1<<m, -1); vi ppl_covered(1<<m, -1); leftover[0] = 0; ppl_covered[0] = 0; rep(s,0,(1<<m)-1){ rep(last,0,m-1){ if((s&(1<<last))==0)continue; int prev = (s & ~(1<<last)); if(ppl_covered[prev] == -1)continue; int new_amt = leftover[prev] + b[last]; int target = a[ppl_covered[prev]]; if(new_amt < target){ ppl_covered[s] = ppl_covered[prev]; leftover[s] = new_amt; } else if(new_amt == target){ ppl_covered[s] = ppl_covered[prev]+1; leftover[s] = 0; } } if(ppl_covered[s] == n){ cout<<"YES\n"; return; } } cout<<"NO\n"; } signed main() { IOS int t=1; // cin>>t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...