Submission #1189651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189651		yoruonivamp	Bank (IZhO14_bank)	C++20	44 / 100	70 ms	328 KiB

bank

// YoruoniVamp - VTUBE
// Pragma Credit to Discord: pxsithexahydride
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,no-stack-protector,inline-small-functions,inline,unsafe-math-optimizations,omit-frame-pointer,inline-functions-called-once")
#include <bits/stdc++.h>
#pragma GCC target("avx2,fma,popcnt,lzcnt,bmi,bmi2,sse4.2,tune=native")
using namespace std;
#define endl '\n'
#define ll long long
#define ld long double
#define ull unsigned ll
#define cint const int
#define cf const float

cint mxA = 1e6+5, MOD = 1e9+7, INF = 0x3f3f3f3f;
cint d4x[4] = {0, 1, 0, -1}, d4y[4] = {1, 0, -1, 0};
cint d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1}, d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

void wait(int ms){
    clock_t endwait;
    endwait = clock() + ms;
    while(clock()<endwait){}
}

ll a[21], b[21];
ll dp[21], bm[21];
ll n, m;
bool valid;

void knap(int idx){
    if(idx==n+1){
        // for(int i = 1; i <= n; i++){
        //     int ii = 0;
        //     int tmp = bm[i];
        //     string s = "";
        //     while(tmp){
        //         if(tmp&1) s+='1';
        //         else s+='0';
        //         tmp>>=1;
        //         ii++;
        //     }for(;ii<m;ii++)s+='0';
        //     // reverse(s.begin(),s.end());
        //     cout << s << endl;
        //     // cout << endl;
        // }
        cout << "YES";
        exit(0);
    }for(ll mask = 1; mask <= ((1<<m)-1); mask++){
        // cout << mask << endl;
        bool canchoose = true;
        for(int j = 1; j <= n; j++){
            ll tmp = bm[j];
            if(tmp&mask){
                canchoose = false;
                break;
            }
        }if(canchoose){
            ll tmp = mask;
            int i = 1;
            while(tmp){
                if(tmp&1) dp[idx] += b[i];
                i++;
                tmp>>=1;
            }
        }if(dp[idx]==a[idx]){
            bm[idx] = mask;
            knap(idx+1);
        }dp[idx] = 0;
        // cout << "TO END" << endl;
    }
}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];
    if(m<n) goto fail;
    knap(1);
    fail:
    cout << "NO";
    return;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(0);cout.tie(0);
    // freopen("", "r", stdin);
    // freopen("", "w", stdout);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

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