AOJ 2333 My friends are small

まず、wを昇順でソートする。
dp[i][j] = #{w[i]以降のみを使って和がjとなる組}
sum[i] = w[i]までの和
とするとき、次の3つの場合を考えれば良い。

(i) w[0]を使わない
(ii) w[0]からw[i]までを使い、w[i+1]を使わない(0 <= i < N-1)
(iii) 全て使う

(i)の場合, (i=1,j) s.t. 0 <= W - j < w[0] について、dp[i][j]をresに加える
(ii)の場合、 (i,j) s.t. 0 <= W - sum[i] - j < w[i+1] について、dp[i][j]をresに加える
(iii)の場合、 W >= sum[N-1] ならばresに1を加える。

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

const int INF = 1e9;
const int MOD = 1000000007;

int main() {
  int N,W;
  cin >> N >> W;
  vector<int> w(N),sum(N);
  REP(i,N) cin >> w[i];
  sort(ALL(w));
  sum[0] = w[0];
  REP(i,N-1) sum[i+1] = sum[i] + w[i+1];
  
  vector<vector<int>> dp(N+1, vector<int> (W+1,0));
  dp[N][0] = 1;
  for(int i=N-1;i>=0;i--)REP(j,W+1){
    if(j >= w[i]) dp[i][j] += dp[i+1][j-w[i]];
    dp[i][j] += dp[i+1][j];
    dp[i][j] %= MOD;
  }

  int res = 0;
  if(W >= sum[N-1]) res++;
  REP(j,W+1) if(j > W - w[0]){
    res = (res + dp[1][j]) % MOD;
  }
  REP(i,N-1)REP(j,W+1){
    if(j > W - sum[i+1] && j <= W - sum[i]){
      res = (res + dp[i+2][j]) % MOD;
    }
  }
  cout << res << endl;
  return 0;
}