Submission #1775776

---

Source Code Expand

#include <bits/stdc++.h>
const int N = 5050;
using namespace std;
bool c[N][N],b[N][N];
short int g[N][N],f[N][N];
int a[N];
int main(){
  int n,k; cin>>n>>k;
  for (int i=1; i<=n; ++i)
    cin>>a[i];
  g[0][0]=f[n+1][0]=1;
  for (int i=1; i<=n; ++i)
    for (int j=0; j<=k; ++j)
      if (g[i-1][j]){
	g[i][j]=1;
	if (j+a[i]<=k)
	  g[i][j+a[i]]=1;
      }
  for (int i=n; i>=1; --i)
    for (int j=0; j<=k; ++j)
      if (f[i+1][j]){
	f[i][j]=1;
	if (j+a[i]<=k)
	  f[i][j+a[i]]=1;
      }
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=k; ++j){
      b[i][j]=g[i][j],c[i][j]=f[i][j];
      f[i][j]+=f[i][j-1],g[i][j]+=g[i][j-1];
    }
  int ans=0,w;
  for (int i=1; i<=n; ++i){
    w=0;
    for (int j=0; j<k; ++j)
      if (j+a[i]>=k&&(b[i-1][j]||c[i+1][j]))
	{ w=1; break; }
    if (!w){
      for (int j=0; j<k; ++j){
	if (b[i-1][j]&&(f[i+1][k-j-1]-f[i+1][k-j-a[i]-1])>0)
	  { w=1; break; }
	if (c[i+1][j]&&(g[i-1][k-j-1]-g[i-1][k-j-a[i]-1])>0)
	  { w=1; break; }
      }
    }
    ans+=(w^1);
  }
  cout<<ans;
  return 0;
}

Submission Info

Judge Result