Submission #948885

#TimeUsernameProblemLanguageResultExecution timeMemory
948885tnknguyen_Bank (IZhO14_bank)C++14
100 / 100
103 ms17236 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define MASK(k) (1LL<<k) #define pii pair<int, int> int n, m; int a[30], b[30]; // ------------ SUBTASKS ------------ namespace SUB1{ bool ok(){ return (n == 1); } void solve(){ vector<int> f(1e3+5, 0); f[0] = 1; for(int i=1; i<=m; ++i){ for(int j=a[1]; j>=b[i]; --j){ f[j] |= f[j - b[i]]; } } cout<<(f[a[1]] ? "YES" : "NO"); //----------------------------- exit(0); } } int v[21][MASK(21)]; int f[21][MASK(21)]; namespace SUB23{ bool ok(){ return (m <= 14); } void solve(){ for(int i=0; i<MASK(m); ++i){ int sum = 0; for(int j=i; j!=0; j-=(j&-j)){ sum += b[__lg((j&-j)) + 1]; } for(int j=1; j<=n; ++j){ if(a[j] == sum){ v[j][i] = 1; } } } f[0][0] = 1; int fl = 1; for(int i=1; i<=n; ++i){ int b = 0; for(int y=0; y<MASK(m); ++y){ if(f[i-1][y] == 1){ for(int x=0; x<MASK(m); ++x){ if((x & y) == 0 && v[i][x] == 1){ f[i][x | y] = 1; b = 1; } } } } if(!b){ fl = 0; break; } } cout<<(fl ? "YES" : "NO"); //----------------------------- exit(0); } } pii g[MASK(21) + 5]; namespace SUB4{ void solve(){ for(int i=0; i<MASK(m); ++i){ g[i] = {0, 0}; } int ans = 0; for(int i=0; i<MASK(m); ++i){ int k = g[i].first, w = g[i].second; for(int j=0; j<m; ++j){ if((MASK(j) & i)){ continue; } int msk = (i | MASK(j)); pii nxt = {k, w + b[j+1]}; if(w + b[j+1] == a[k+1]){ nxt = {k+1, 0}; } g[msk] = (nxt.first > g[msk].first ? nxt : g[msk]); //take pair with larger first value. g[msk] = max(g[msk], nxt); } ans = max(ans, g[i].first); } cout<<(ans >= n ? "YES" : "NO"); //----------------------------- exit(0); } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("main.inp","r",stdin); //freopen("main.out","w",stdout); //f[mask][i] = cin>>n>>m; for(int i=1; i<=n; ++i){ cin>>a[i]; } for(int j=1; j<=m; ++j){ cin>>b[j]; } // if(SUB1::ok()){ // SUB1::solve(); // } // if(SUB23::ok()){ // SUB23::solve(); // } SUB4::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...