Submission #2240436

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli>> mat;
typedef vector<unordered_map<lli,lli>> graph;

lli n,k;
vll a;

mat dp;
mat pd;

lli ans = 0;

int main(){
  cin >> n >> k;
  a = vll(n+1);
  for(lli i = 1;i <= n;i++) cin >> a[i];
  dp = mat(n+2,vll(k+1));
  pd = mat(n+2,vll(k+1));
  dp[0][0] = 1;
  for(lli i = 1;i <= n;i++){
    for(lli j = 0;j < a[i] && j <= k;j++){
      dp[i][j] = dp[i-1][j];
    }
    for(lli j = a[i];j <= k;j++){
      dp[i][j] = dp[i-1][j]|dp[i-1][j-a[i]];
    }
  }
  pd[n+1][0] = 1;
  for(lli i = n;i >= 1;i--){
    for(lli j = 0;j < a[i] && j <= k;j++){
      pd[i][j] = pd[i+1][j];
    }
    for(lli j = a[i];j <= k;j++){
      pd[i][j] = pd[i+1][j]|pd[i+1][j-a[i]];
    }
  }
  for(lli i = 1;i <= n;i++){
    lli x,y;
    lli bound = 0;
    x = 0;y = k;
    while(true){
      while(x <= k && dp[i-1][x] == 0)x++;
      while(y >= 0 && pd[i+1][y] == 0)y--;
      if(x > k || y < 0) break;
      if(x+y >= k)y--;
      else{
        bound = max(bound,x+y);
        x++;
      }
    }
    if(bound+a[i] >= k) ans++;

  }
  cout << n-ans << endl;
  return 0;

}

Submission Info

Judge Result