Submission #1306713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306713		hectormedrano	Bank (IZhO14_bank)	C++20	71 / 100	1102 ms	212540 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(w<5e5 and vis[w][x]){return DP[w][x];}
    if(w<5e5){vis[w][x] = true;}
    if(x==0){
        if(w<5e5){DP[w][x] = true;}
        return true;
    }
    if(w==0){
        if(w<5e5){DP[w][x] = false;}
        return false;
    }
    bool r = 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;}
        r = (r or calc(w-val, x-1));
    }
    if(w<5e5){DP[w][x] = r;}
    return r;
}

int main() {
    cin>>N>>M;
    a.resize(N);
    b.resize(M);
    s.resize(1<<M);
    c.resize(N);
    vis.resize(5e5, vector<ll>(N+1, false));
    DP.resize(5e5, 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());
    for(ll i=0;i<N;i++){
        pair<ll, ll> p1 = {a[i], 1<<M};
        pair<ll, ll> p2 = {a[i], -1};
        auto it1 = upper_bound(s.begin(), s.end(), p1);
        auto it2 = lower_bound(s.begin(), s.end(), p2);
        if(it2 == s.end()){continue;}
        ll x, y;
        if(it1 == s.end()){x = 1<<M;}
        else{x = it1 - s.begin();}
        y = it2 - s.begin();
        for(ll j=y;j<x;j++){
            c[i].push_back(s[j].second);
        }
    }
    if(calc((1<<M) - 1, N)){cout<<"YES";}
    else{cout<<"NO";}
}

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