제출 #1153007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153007		MrDeboo	Bank (IZhO14_bank)	C++20	0 / 100	1094 ms	33164 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);
int n,m;
vector<int>v(n),vv(m);
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;
    swap(n,m);
    swap(v,vv);
    sort(vv.begin(),vv.end(),greater<int>());
    pre();
    for(int i=1;i<(1<<n);i++){
        for(int w=i;w;w=(w-1)&i){
            int ww=(w^i);
            int b=(bt[w]|bt[ww]),a=eq[i]-eq[b];
            for(int j=0;j<m;j++){
                if(((b&(1<<bt[w]))==0)&&vv[j]<=a){
                    a-=vv[j];
                    b|=(1<<bt[w]);
                }
            }
            if(__builtin_popcount(b)>__builtin_popcount(bt[w])){
                bt[w]=b;
            }
        }
    }
    cout<<(__builtin_popcount(bt[(1<<n)-1])==m?"YES":"NO");
}

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