第７回日本情報オリンピック 本選 C-ダーツ（精選23）

問題

https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf#page=6

ダーツを４本まで投げ上限Mを超えない得点の最大値を求めます。
得点はP[N]でN<＝１０００です。

考察

普通にループを回すのでは1000^4=１兆になりとても間に合いません。
二分探索のパワーを十分に使うため２本づつ投げることにすると間に合います。
投げない場合を考えて得点の配列に０を加えます。

upper_boundで出力したitr（Mを超える最初の要素のitr）の１つ前の要素（*(itr－1)）の最大値を出力します。

ACしたコード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int N,M;
  cin>>N>>M;
  vector<int>P(N+1);
  vector<int>Q((N+1)*(N+1));
  for(int i=1;i<=N;i++){
    cin>>P[i];
  }
  P[0]=0;
  int ans=0;
  for(int i=0;i<=N;i++){
    for(int j=0;j<=N;j++){
      Q[i*(N+1)+j]=P[i]+P[j];
    }
  }
  sort(Q.begin(),Q.end());
  for(int i=0;i<(N+1)*(N+1);i++){
    if(Q[i]>M) break;
    auto itr=upper_bound(Q.begin(),Q.end(),M-Q[i]);
    ans=max(ans,Q[i]+*(itr-1));
  }
  cout<<ans<<endl;
}