제출 #1153076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153076		MrDeboo	은행 (IZhO14_bank)	C++20	52 / 100	1097 ms	25072 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>());
    sort(vv.begin(),vv.end(),greater<int>());
    map<int,int>a,b,c;
    for(auto &i:v)a[i]++;
    for(auto &i:vv)b[i]++;
    for(auto &i:a)c[i.first]=min(b[i.first],i.second);
    vector<int>vov,vovv;
    map<int,int>d=c;
    for(auto &i:v){
        if(c[i])c[i]--;
        else vov.push_back(i);
    }
    c=d;
    for(auto &i:vv){
        if(c[i])c[i]--;
        else vovv.push_back(i);
    }
    v=vov;
    vv=vovv;
    if(v.size()==0){
        cout<<"YES";
        return 0;
    }
    if(v.size()*2>vv.size()){
        cout<<"NO";
        return 0;
    }
    n=v.size();
    m=vv.size();
    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: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29