Submission #1730694

---

Source Code Expand

#include <iostream>
#include <fstream>
using namespace std;
const int nmax=5025;
int dp[2][nmax][nmax];
int a[nmax],l[nmax],r[nmax];
int n,i,j,k,ind,n1,n2,ans;
bool check()
{
    ind=1;
    for(j=n1;j>=1;j--)
    {
        while(ind<=n2&&l[j]+r[ind]<k) ind++;
        ind--;
        if(l[j]+r[ind]>=k-a[i])
            return 1;
    }
    return 0;
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>k;
    dp[0][0][0]=1;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        for(j=0;j<=k;j++)
            dp[0][i][j]=dp[0][i-1][j];
        for(j=k-a[i];j>=0;j--)
            dp[0][i][j+a[i]]|=dp[0][i][j];
    }
    dp[1][n+1][0]=1;
    for(i=n;i>=1;i--)
    {
        for(j=0;j<=k;j++)
            dp[1][i][j]=dp[1][i+1][j];
        for(j=k-a[i];j>=0;j--)
            dp[1][i][j+a[i]]|=dp[1][i][j];
    }
    for(i=1;i<=n;i++)
    {
        n1=n2=0;
        for(j=0;j<k;j++)
            if(dp[0][i-1][j])
               l[++n1]=j;
        for(j=0;j<k;j++)
            if(dp[1][i+1][j])
               r[++n2]=j;
        if(!check()) ++ans;
    }
    cout<<ans;
    return 0;
}

Submission Info

Judge Result