Submission #1306701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306701		hectormedrano	Bank (IZhO14_bank)	C++20	19 / 100	213 ms	132196 KiB

bank

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

ll N, M;
vector<ll> a, b;
vector<pair<ll, ll>> s;
vector<vector<ll>> c;
vector<vector<ll>> vis;
vector<vector<ll>> DP;

bool calc(ll w, ll x){
    if(vis[w][x]){return DP[w][x];}
    vis[w][x] = true;
    if(x==0){return DP[w][x] = true;}
    if(w==0){return DP[w][x] = false;}
    DP[w][x] = false;
    ll w_ = (1<<M) - 1 - w;
    for(ll val : c[x-1]){
        //cout<<"Para "<<w<<" y "<<x<<": "<<w_<<" "<<val<<endl;
        if((w_ xor val) != (w_ + val)){continue;}
        DP[w][x] = (DP[w][x] or calc(w-val, x-1));
    }
    return DP[w][x];
}

int main() {
    cin>>N>>M;
    a.resize(N);
    b.resize(M);
    s.resize(1<<M);
    c.resize(N);
    vis.resize((1<<M), vector<ll>(N+1, false));
    DP.resize((1<<M), vector<ll>(N+1, false));
    for(ll i=0;i<N;i++){cin>>a[i];}
    for(ll i=0;i<M;i++){cin>>b[i];}
    sort(a.begin(), a.end());
    s[0] = {0, 0};
    for(ll i=1;i<=M;i++){
        for(ll j=(1<<(i-1));j<(1<<i);j++){
            s[j].first = s[j-(1<<(i-1))].first + b[i-1];
            s[j].second = j;
            //cout<<s[j].first<<endl;
        }
    }
    //for(pair<ll, ll> val : s){cout<<val.first<<endl;}
    sort(s.begin(), s.end());
    ll ind = 0;
    bool rng = false;
    for(ll i=0;i<(1<<M);i++){
        if(ind==N){break;}
        if(s[i].first == a[ind]){
            c[ind].push_back(s[i].second);
            //cout<<bitset<4>(s[i].second)<<" da "<<a[ind]<<endl;
            rng = true;
        } else {
            if(rng){ind++;}
            rng = false;
        }
    }
    if(calc((1<<M) - 1, N)){cout<<"YES";}
    else{cout<<"NO";}
}

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