第７回日本情報オリンピック 本選 「ダーツ」

解法：半分全列挙
粘り勝ち。

実際WA続いたのはAOJがサーバーの負担を減らすためにテストデータをまとめた結果初期化が必要になってそれを忘れていただけだからたぶん本番はﾀﾞｲｼﾞｮﾌﾞ。

計算量はO(N^2logN).まあ典型のやつですね。

蟻本を読もう。

#include <cstdio>
#include <algorithm>
#include <string.h>

using namespace std;

int n,d[1004],m;
int h[1010000];
int ki;

bool nib(int x){
  return h[x] > ki;
}

int main(){
  
  while(1){
  memset(d,0,sizeof(d));
  memset(h,0,sizeof(h));
  scanf("%d%d",&n,&m);
  if(n == 0)break;
  
  int ans = 0;
  for(int i = 0;i < n;i++){
    scanf("%d",&d[i]);
  }
  
  for(int i = 0;i <= n;i++){
    for(int j = 0;j <= n;j++){
      h[i * n + j] = d[i] + d[j];
    }
  }

  sort(h,h + (n+1)*(n+1));
  
  for(int i = 0;i <= n;i++){
    for(int j = 0;j <= n;j++){
      int ch = d[i] + d[j];
      ki = m - ch;
      if(ki < 0)continue;
      int lb = -1,ub = n*n+n+1;
      while(ub - lb > 1){
	int mid = (ub + lb) / 2;
	if(nib(mid)) ub = mid;
	else lb = mid;
      }

   if(ch+h[lb] <= m) ans = max(ans,ch+h[lb]);
    }
  }
  
  printf("%d\n",ans);
  
  }
  
  return 0;
}