Submission #1179485

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

int N,K;
long long a[5000];
int dp[5000][5000];

int rec(int x, int y);
bool need(int i);


int main(){
    int ans;
    int left,right;

    scanf("%d %d", &N,&K);
    for(int i=0;i<N;i++){
        scanf("%lld",&a[i]);
    }

    sort(a,a+N);

    if(need(0)==true){
        ans = 0;
    }else if(need(N-1)==false){
        ans = N;
    }else{
        left = 0;
        right = N-1;

        while(left<right-1){
            int m = (right - left) / 2 + left;
            if(need(m)){
                right = m;
            }else{
                left = m;
            }
        }

        ans = right;
    }
        printf("%d\n",ans);

        return 0;
}


int rec(int x,int y){
    if(dp[x][y]>=0){
        return dp[x][y];
    }
    if(x==0){
        if(a[0]==y) return 1;
        else return 0;
    } else {
        int res = 0;
        if(rec(x-1,y)==1){
            res = 1;
        }
        if(y>=a[x]){
            if(rec(x-1,y-a[x])==1){
                res = 1;
            }
        }
        dp[x][y] = res;
        return res;
    }
}


bool need(int i){
    int temp = a[i];
    a[i] = 0;
    memset(dp,-1,sizeof(dp));
    bool found = false;

    for(int j=max(0,K-temp);j<K;j++){
        if(rec(N-1,j)==1){
            found = true;
            break;
        }
    }
    a[i] = temp;
    return found;
}

Submission Info

Compile Error

./Main.cpp: In function ‘bool need(int)’:
./Main.cpp:76:28: error: ‘memset’ was not declared in this scope
     memset(dp,-1,sizeof(dp));
                            ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:18:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N,&K);
                          ^
./Main.cpp:20:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&a[i]);
                            ^