Submission #1280805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280805		iq500	은행 (IZhO14_bank)	C++20	25 / 100	1096 ms	9640 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; 
bool *dp;
int *vals;
bool ans=false;

bool f(int ind, int s){
    if(ind>=n) {ans=true; return 1;}
    if(dp[s]) 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);
        else if(vals[add]==pref[ind]) ret|=f(ind+1, add);
    }
    return dp[s]=ret;
}

signed main()
{
    cin>>n>>m;
    dp=(bool*)calloc(1<<m, sizeof(bool));
    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++){
        int add=0;
        for(int j=0; j<m; j++){
            if((1<<j)&i) add+=b[j];
        }
        vals[i]=add;
    }
    f(0, 0);
    /*for(int i=0; i<(1<<m); i++) cout<<i<<": "<<dp[i]<<"\n";
        cout<<"\n";*/
    if(ans) cout<<"YES";
    else cout<<"NO";

    return 0;
}

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