0530 Darts (ダーツ)

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0529
N 個の得点が与えられ，この中から4つまで選んでその合計を最大値を求める問題．
ただし，合計が M を超えてしまった場合は 0 点になってしまう．

最初 DP でいけるかと思ったけど，サンプルは通ったものの WA だった．
投げられるダーツの矢は4本と限られているので，まず 2 本投げたときにとりうる得点を列挙しこれを v とし，
各 v の要素において，合計が M を超えない v の要素を二分探索で求めてそれの最大値を答えとするコードを書いた．
4本投げない場合もあるので，v に 0 と各得点そのものも入れる必要があることに注意．
N <= 1000 で O(N^2 log N) なので間に合う．

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
  int N, M;
  while (cin >> N >> M && N != 0) {
    vector<int> ps(N);
    for (int i = 0; i < N; i++) {
      cin >> ps[i];
    }

    vector<int> v(1, 0);
    for (int i = 0; i < N; i++) {
      v.push_back(ps[i]);
      for (int j = i; j < N; j++) {
        if (ps[i] + ps[j] <= M) {
          v.push_back(ps[i] + ps[j]);
        }
      }
    }
    sort(v.begin(), v.end());

    int ans = 0;
    for (vector<int>::const_iterator it(v.begin()); it != v.end(); ++it) {
      vector<int>::const_iterator jt = lower_bound(v.begin(), v.end(), M - *it);
      if (jt != v.begin()) {
        --jt;
        ans = max(ans, *it + *jt);
      }
    }
    cout << ans << endl;
  }
  return 0;
}