Submission #923452

#	Time	Username	Problem	Language	Result	Execution time	Memory
923452		_saketks_07	Bank (IZhO14_bank)	C++14	46 / 100	80 ms	25172 KiB

bank

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
///  order_of_key return number of elements less than x.
///  find_by_order return index.

const int N =  3*1e5 + 10;
const int M = 998244353;

#define ll long long int
#define ld long double
#define rep(i, n) for (ll i = 0; i < n; i++)
#define ff first
#define ss second
#define rep1(i, n) for (ll i = 1; i < n; i++)
#define repr(i, n) for (ll i = n - 1; i >= 0; i--)
#define pb push_back
#define vi vector<int>
#define vll vector<long long>
#define vpll vector<pair<ll, ll>>
#define vvll vector<vector<ll>>
#define vvpll vector<vector<pll>>
#define pll pair<ll, ll>
const ll INF = 1e9+7;
ll binmult(int a, int b)
{
    ll ans = 0;
    while (b > 0)
    {
        if (b & 1)
            ans = (ans + a) % M;
        a = (a + a) % M;
        b >>= 1;
    }
    return ans;
}
ll binpow(int a, int b)
{
    ll ans = 1;
    while (b > 0)
    {
        if (b & 1)
            ans = binmult(ans, a);
        a = binmult(a, a);
        b >>= 1;
    }
    return ans;
}
ll bs_sqrt(ll x)
{
    ll left = 0, right = 2000000123;
    while (right > left)
    {
        ll mid = (left + right) / 2;
        if (mid * mid > x)
            right = mid;
        else
            left = mid + 1;
    }
    return left - 1;
}
ll inverse(ll x,ll M){
    ll y=binmult(x,M-2);
    return y;
}

// ll nCr(ll n, ll r)
// {
//     return ((fac(n)*inverse(fac(n-r)))%M*inverse(fac(r)))%M;
// }

//----------------------------------------------------------------------
// DSU
// vll par(N+1,0),sz(N+1,0);
// void make(int x){
//     par[x]=x;sz[x]=1;
// }
// int find(int x){
//     if(x==par[x]) return x;
//     return par[x]=find(par[x]);
// }
// void Union(int b,int a){
//     a=find(a),b=find(b);
//     // if(a!=b)
//     {
        
//         if(sz[a]<sz[b]) swap(a,b);
//         sz[a]+=sz[b];
//         par[b]=a;
//     }
// }
//--------------------------------------------------------------------
// Dynamic Range Minimum Segment Tree

// vll a(N), seg(4*N);
// void build(int ind, int low, int high){
//     if(low==high) {seg[ind]=a[low]; return ;}
//     ll mid=(high+low)/2;
//     build(2*ind+1, low, mid);
//     build(2*ind+2, mid+1,high);
//     seg[ind]=min(seg[2*ind+1], seg[2*ind+2]);
// }
// void update(ll ind, ll low,ll high, ll i, ll val){
//     if(low==high ){
//         if(low==i)
//         seg[ind]=val;
//         return ;
//     }
//     if(i<low || i>high) return ;
//     ll mid=(high+low)/2;
//     update(2*ind+1,low, mid, i, val);
//     update(2*ind+2,mid+1, high, i, val);
//     seg[ind]=min(seg[2*ind+1], seg[2*ind+2]);
//     return ;
// }
// ll query(ll ind, ll low,ll high, ll l, ll r){
//     if(l<=low && high<=r) return seg[ind];
//     if(high< l || low>r) return INT_MAX;
//     ll mid=(high+low)/2;
//     return min(query(2*ind+1, low, mid, l, r), query(2*ind+2, mid+1, high, l, r));
// }
//-----------------------------------------------------------------------


// void dfs(ll i,ll s,vvll &g, vll &dis,vvll &dp){
//     ll ans=dis[i];
//     for(auto it: g[i]){
//         if(dp[i][s]==INF) {
//             if(dis[it] > dis[i]) 
//             {    dfs(it,s,g,dis,dp);
//                  ans=min(ans, dp[it][s]);
//             }
//             else{
//                 if(s==0)
//                 {dfs(it,1,g,dis,dp);
//                 ans=min(ans, dp[it][1]);}
//             }

//         }   
//         else{
//             if(dis[it] > dis[i])
//             ans=min(ans, dp[it][s]);
//             if(s==0 && dis[it] <= dis[i]) ans=min(ans, dp[it][1]);
//         }
//     }
//     dp[i][s]=ans;
// }

void bfs(vvll &g, vll &vis, vll &dis, ll w, ll s){
    queue<pll> q;
    q.push({0,s});
    // dis[1]=0;
    while(!q.empty()){
        pll cur=q.front(); q.pop();
        if(vis[cur.ss]) continue;
        vis[cur.ss]=1;
        for(auto it:g[cur.ss]){
            if(cur.ff+ 1 < dis[it])
                dis[it]=cur.ff+1; q.push({dis[it],it});
        }
    }
    rep(i,dis.size()) dis[i]=w*dis[i];
}


void solve(){
    ll n,m;cin>>n>>m;
    vll a(n), b(m);
    rep(i,n) cin>>a[i];
    rep(i,m) cin>>b[i];
    vvll mp(n);
    rep(i,(1<<m)){
        ll s=0;
        rep(j,m){
            if((i>>j)&1){
                s+=b[j];
            }
        }
        ll ind=find(a.begin(), a.end(), s)-a.begin();
        if(ind!=n)
        {
            mp[ind].pb(i);
        }
    }
    vvll dp(n+1,vll((1<<m)+1,0));
    for(auto it : mp[0]) {dp[0][it]=1; }
        // cout<<it<<" ";}
    // cout<<endl;
    rep1(i,n){
        rep(j,(1<<m)){
            for(auto it: mp[i]){
                if((it&j)!=it) continue;
                dp[i][j]|=dp[i-1][j^it];
            }
        }
    }
    ll ok=0;
    
    rep(j,1<<m){
        if(dp[n-1][j]==1) {
            // cout<<j<<" ";
            ok=1;
        }
    }
    if(ok) cout<<"YES\n";
    else cout<<"NO\n";
}

    int main()
    {
        // freopen("pails.in", "r", stdin);
        // freopen("pails.out", "w", stdout);
        
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        int t=1;
        // cin >> t;
        ll tt = 1;
        ll p=1;
        while (t--)
        {    
            solve();
            tt++;
        }
        return 0;
    }
 
/*
to get the maxsum, and minsum of a array from start but processing from end:-
suppose s is the array, sul - suffix_minsum, sur - suffix_maxsum
for (int i = n - 1; i >= 0; --i){
            int d = s[i];
            sul.push_back(min(0, sul.back() + d));
            sur.push_back(max(0, sur.back() + d));
}
*/

Compilation message (stderr)

bank.cpp: In function 'void bfs(std::vector<std::vector<long long int> >&, std::vector<long long int>&, std::vector<long long int>&, long long int, long long int)':
bank.cpp:163:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  163 |             if(cur.ff+ 1 < dis[it])
      |             ^~
bank.cpp:164:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  164 |                 dis[it]=cur.ff+1; q.push({dis[it],it});
      |                                   ^
bank.cpp:17:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define rep(i, n) for (ll i = 0; i < n; i++)
......
  167 |     rep(i,dis.size()) dis[i]=w*dis[i];
      |         ~~~~~~~~~~~~                
bank.cpp:167:5: note: in expansion of macro 'rep'
  167 |     rep(i,dis.size()) dis[i]=w*dis[i];
      |     ^~~
bank.cpp: In function 'int main()':
bank.cpp:225:12: warning: unused variable 'p' [-Wunused-variable]
  225 |         ll p=1;
      |            ^

• Subtask 1: 19 / 19
• Subtask 2: 0 / 25
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29