AOJ2176 For the Peace

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2176

N個の国がある。各々の国に対して、逆時系列順に新たに作ったミサイルの強さがM[i]個ずつ与えられる。
国力とは、持っているミサイルの強さの和で定義される。
ミサイルを破棄するには、持っている中で最も新しいミサイルから破棄する必要がある。
どの国同士の国力の差がD以下に収まっていれば、国同士の強さのバランスが保たれる。
適切な順序で破棄していったとき、国同士の強さのバランスを保ったまま全てのミサイルを破棄することは可能か。
N <= 100, D <= 1000
ΣM[i] <= 10000

解説
国同士の国力の差がD以下となって破棄できるミサイルのうち、最大の強さを持つミサイルを破棄していけば良い。

int main() {
 
  for(int N, D; cin >> N >> D && (N|D);) {
    vector<vector<int>> C(N);
    vector<int> idx(N), curr(N);
    rep(i, N) {
      int M; cin >> M;
      C[i].resize(M);
      rep(j, M) cin >> C[i][j], curr[i] += C[i][j];
      reverse(all(C[i]));
    }
 
    auto getMaxValExceptMe = [&](int idx) {
      int ret = 0;
      rep(i, N) {
        if(i == idx) continue;
        ret = max(ret, curr[i]);
      }
      return ret;
    };
 
    while(1) {
      int maxMin = -1, maxMinIdx = -1;
      bool ok = 0;
      rep(i, N) {
        if(idx[i] < C[i].size()) {
          ok = 1;
          if(curr[i] - C[i][idx[i]] > maxMin && getMaxValExceptMe(i) - (curr[i] - C[i][idx[i]]) <= D) {
            maxMin = curr[i] - C[i][idx[i]];
            maxMinIdx = i;
          }
        }
      }
 
      if(!ok) break;
 
      if(maxMinIdx == -1) {
        cout << "No" << endl;
        goto next;
      }
 
      curr[maxMinIdx] -= C[maxMinIdx][idx[maxMinIdx]];
      idx[maxMinIdx] ++;
    }
 
    cout << "Yes" << endl;
 
    next:;
  }
   
  return 0;
}