JOI本選過去問 第7回 日本情報オリンピック本選 3問目 ダーツ

まず初めに、非常に効率の悪い解法。(O(n^4))

#include <cstdio>
#include <algorithm>

using namespace std;


int n = 0;

long int m = 0;

long int ans = 0;

long int p[1003] = {0};

int main(){

  while(1){


  scanf("%d%ld",&n,&m);

  if(n == 0) break;

  ans = 0;

  for(int i = 0;i < n;i++){
    scanf("%ld",&p[i]);
  }

  sort(p,p+n);




  for(int a = 0;a < n;a++){
    if(p[a] <= m && p[a] > ans) ans = p[a];
    if(p[a] > m) break;


    for(int b = a;b < n;b++){
      long int tmp = p[a] + p[b];
      if(tmp > ans && tmp <= m) ans = tmp;
      if(tmp > m) break;


      for(int c = b;c < n;c++){
	tmp = p[a] + p[b] + p[c];
	if(tmp > ans && tmp <= m) ans = tmp;
	if(tmp > m) break;


	for(int d = c;d < n;d++){
	  tmp = p[a] + p[b] + p[c] + p[d] ;
	  if(tmp > ans && tmp <= m) ans = tmp;
	  if(tmp > m) break;
	}
      }
    }
  }

  printf("%ld\n",ans);

  }


  return 0;

}

次に満点解法といきたかったけどやっぱ寝ます。。。

続きは追記します。