Submission #1280885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280885		iq500	Bank (IZhO14_bank)	C++20	100 / 100	227 ms	16840 KiB

bank

//ghost rule - deco*27
#include <bits/stdc++.h>
#define int long long
using namespace std;

int a[21], b[21], pref[21];
int n, m; 
int *dp;
int *vals;
bool ans=false;

bool f(int ind, int s){

    if(ind>=n) {ans=true; return 1;}
    if(dp[s]!=-1){return dp[s];}

    bool ret=0;
    for(int i=0; i<m; i++){
        if(s&(1<<i)) continue;
        int add=s|(1<<i);
        if(vals[add]<pref[ind]) ret|=f(ind, add);
        if(ret) break;
        else if(vals[add]==pref[ind]) ret|=f(ind+1, add);
        if(ret) break;
    }
    return dp[s]=ret;
}

signed main()
{
    cin>>n>>m;
    dp=(int*)malloc((1<<m)*sizeof(int));
    vals=(int*)calloc(1<<m, sizeof(int));

    for(int i=0; i<n; i++){
        cin>>a[i];
        pref[i]+=a[i];
        if(i!=0) pref[i]+=pref[i-1];
    }

    for(int i=0; i<m; i++) cin>>b[i];

    for(int i=0; i<(1<<m); i++){
        dp[i]=-1;
        int add=0;
        for(int j=0; j<m; j++){
            if((1<<j)&i) add+=b[j];
        }
        vals[i]=add;
    }

    f(0, 0);

    if(ans) cout<<"YES";
    else cout<<"NO";

    return 0;
}

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