Submission #1309780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309780		avrdr101	은행 (IZhO14_bank)	C++20	52 / 100	1099 ms	82268 KiB

bank

#include<bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("popcnt")


#define pb push_back
#define endl "\n"

// typedef long long ll;
// typedef long long int;
#define int long long
typedef pair<int, int> ii; 
typedef vector<pair<int,int>> vii;
typedef vector<int> vi;
typedef vector<vector<int>>vvi;
typedef vector<vector<pair<int,int>>>vvii;
typedef vector<bool> vb;

#define foj(i,l,r,jmp) for(int i=l;i<=r;i+=jmp)
#define foij(i,r,l,jmp) for(int i=r;i>=l;i-=jmp)
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define foi(i,r,l) for(int i=r;i>=l;i--)

//short hand for usual tokens
#define pb push_back
#define fi first
#define se second

// to be used with algorithms that processes a container Eg: find(all(c),42)
#define all(x) (x).begin(), (x).end() //Forward traversal
#define rall(x) (x).rbegin(), (x).rend() //reverse traversal

// traversal function to avoid long template definition. Now with C++11 auto alleviates the pain.
#define tr(c,i) for(__typeof__((c)).begin() i = (c).begin(); i != (c).end(); i++)

// find if a given value is present in a container. Container version. Runs in log(n) for set and map
#define present(c,x) ((c).find(x) != (c).end())

//find version works for all containers. This is present in std namespace.
#define cpresent(c,x) (find(all(c),x) != (c).end())

// Avoiding wrap around of size()-1 where size is a unsigned int.
#define sz(a) int((a).size())

//input integer and string
#define takei(n) int n; cin >> n
#define takel(n) ll n; cin >> n
#define takes(s) string s; cin >> s
#define takei2(a, b) int a, b; cin >> a >> b
#define takei3(a, b, c) int a, b, c; cin >> a >> b >> c
#define takei4(a, b, c, d) int a, b, c, d; cin >> a >> b >> c >> d
#define takea0(a,n) for(int i=0;i<n;i++)cin>>a[i]
#define takea1(a,n) for(int i=1;i<=n;i++)cin>>a[i]
#define takedg(adj,m) for(int i=1,a,b;i<=m;i++)cin>>a>>b,adj[a].pb(b)
#define takeudg(adj,m) for(int i=1,a,b;i<=m;i++)cin>>a>>b,adj[a].pb(b),adj[b].pb(a)

#define oute(n) cout<<n<<"\n"
#define oute2(x,y) cout<<x<<" "<<y<<"\n"
#define oute3(x,y,z) cout<<x<<" "<<y<<" "<<z<<"\n"
#define out1(x) cout<<x<<" "
#define outl cout<<"\n"
#define outf cout.flush()
#define outa(a,n) for(int i=0;i<(int)n;i++)cout<<a[i]<<" ";

const int MOD=1e9+7,MOD2=998244353;
const int max2n=200005,maxm=100005,maxN=1e9+5,max5n=500005,maxe7=10000005;

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        takei2(n,m);
        vi a(n),b(m);
        takea0(a,n);
        takea0(b,m);
        sort(all(a));
        if(n>m){
            cout<<"NO"<<endl;
            continue;
        }
        int lim=1<<m;
        vector<vb> dp(lim,vb(n));
        vi sum(lim);
        bool can_take=false;
        // int cnt=0;
        fo(mask,1,lim-1){
            int lsb=mask&-mask;
            int bit=__builtin_ctz(lsb);
            sum[mask]=sum[mask^lsb]+b[bit];
            for(int submask=mask;submask!=0;submask=mask&(submask-1)){
                //submask is the current subset taken at the end
                int prev=submask^mask;
                fo(j,0,n-1){
                    // cnt++;
                    if(sum[submask]==a[j] && (j==0 || dp[prev][j-1])){
                        if(j==n-1){
                            //have taken all
                            can_take=true;
                            break;
                        }
                        dp[mask][j]=true;
                    }
                    else if(sum[submask]<a[j]){
                        break;
                    }
                }
                if(can_take){
                    break;
                }
            }
            if(can_take){
                break;
            }
        }
        // cout<<cnt<<endl;
        if(can_take){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
}

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