[2010山東省第一回ACM大学生プログラム設計コンテスト]——Greest Number

Greest Number
タイトル:http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2157
タイトルはSaya likes math、because she think mash can make her cleverを記述します。
One day、Kudo invited a very simple game：
Ginven integers，then the playrs chorose no more than four integers from them(can be repeated)and add the m togethe r.Finally，the one whose sum the large winds the game.It seems verdmper the.emper diultion
Saya is very interest in this game.She says that since the number of integers is finite，we can enumerate all the selecting and find the largest sum.Saya cars the largem Grest Number
Kudo wants to know whether Saya's answer is the best，so she consto you for help.
Can you help her to computte the GN？
The input consists of several test casesを入力します。
The first line of input in each test case contains two integers N（0＜N≦1000）and M（0 100000万）、which represent the number of integers and the up bound.
Each of the next N lineas contains the integers.(Not larger than 100000)
The last case is followwed by line containing two zros.
For each caseを出力して、print the case number（1、2…）and the GN.
Your output format Shoult imitate the sample output.Print a blank line after each test case.
例入力2 10
100
2
0
サンプル出力
Case 1:8
タイトルの要求は N個の数をあげます。4個以上の数で構成してもMより大きくない最大の数で、与えられた数の使用回数は制限しません。
例で説明します。Nは2、Mは10で、つまり2と100で1つを構成して10より大きい最大の数です。
100が10より大きいです。捨てるのは明らかです。残りの2は何回でも使えます。最大4つの数で一つの数を構成するので、2は4回で8を得ます。
この問題の解題の構想は巧みで、一つの数を構成する個数が4以下であることを要求します。私達は0個の数（つまり0）を構成させて、一つの数（入力の数自体）と、任意の二つの数のものを一つの配列に入れます。
このように配列内の任意の2つの数を加算すると、任意の1～4つの数からなる数を表します。
最後に二点で調べて、要求に合うものを探してください。（≧▽≦）/～ラララ
そうだ、検索する前に順序を忘れないでください。

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int arr[1001000];
int N,M;

//     
int binary_sort(int len)
{
    int i,l,h,mid,aim;
    aim=0;
    for(i=0; i<len; ++i)
    {
        l=0;h=len;
        while(l<h)                    //                      
        {
            mid=(l+h)/2;
            if(arr[mid]+arr[i]<=M)
            {
                if(arr[i]+arr[mid]>=aim)
                    aim=arr[i]+arr[mid];
                l=mid+1;
            }
            else
                h=mid;
        }
    }
    return aim;
}
int main()
{
    int i,j,k,len,test,temp;
    test=1;

    while(cin>>N>>M)
    {
        if(!N && !M)    break;
        memset(arr,0,sizeof(arr));
        k=1;
        //          
        for(i=0;i<N;++i)
        {
            cin>>temp;
            if(temp>M)  continue;
            arr[k++]=temp;
        }
        //            ,    .

        len=k;
        //             
        for(i=1;i<len;++i)
            for(j=1;j<len;++j)
                arr[k++]=arr[i]+arr[j];
        //       ，        
        sort(arr,arr+k);

        cout<<"Case "<<test++<<": "<<binary_sort(k)<<endl;
        cout<<endl;
    }
    return 0;
}