Submission #1153075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153075		MrDeboo	Bank (IZhO14_bank)	C++20	0 / 100	1098 ms	49732 KiB

bank

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mod 998244353
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>;
vector<int>bt(1<<21);
vector<int>eq(1<<21,-1);
vector<int>eqq(1<<21,-1);
int n,m;
vector<int>v(n),vv(m);
void pee(int sm=0,int sl=0){
    if(eqq[sl]!=-1)return;
    eqq[sl]=sm;
    for(int i=0;i<m;i++){
        if((1<<i)&sl);
        else pee(sm+vv[i],(sl|(1<<i)));
    }
}
void pre(int sm=0,int sl=0){
    if(eq[sl]!=-1)return;
    eq[sl]=sm;
    for(int i=0;i<n;i++){
        if((1<<i)&sl);
        else pre(sm+v[i],(sl|(1<<i)));
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    v.resize(n);
    vv.resize(m);
    for(auto &i:v)cin>>i;
    for(auto &i:vv)cin>>i;
    sort(v.begin(),v.end(),greater<int>());
    for(int i=1;i<n;i++)assert(v[i]!=v[i-1]);
    pre();
    pee();
    for(int i=1;i<(1<<m);i++){
        for(int w=i;w;w=(w-1)&i){
            int ww=(w^i);
            int b=(bt[w]|bt[ww]),a=eqq[i]-eq[b];
            // if(i==1)cout<<a<<endl;
            for(int j=0;j<n;j++){
                if(((b&(1<<j))==0)&&v[j]==a){
                    a-=v[j];
                    b|=(1<<j);
                }
            }
            if(__builtin_popcount(b)>__builtin_popcount(bt[i])){
                // cout<<i<<' '<<w<<' '<<b<<' '<<__builtin_popcount(b)<<' '<<a<<endl;
                bt[i]=b;
            }
        }
    }
    cout<<(__builtin_popcount(bt[(1<<m)-1])==n?"YES":"NO");
}

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