読者です 読者をやめる 読者になる 読者になる

AOJ0529 Darts

JOI2007 本選の3番
蟻本のくじびきのやつみたいに2本ずつにわけて2分探索すれば間に合います

#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;

int n, m, ans, fact;
int k, lb, ub;
int target[1000], tars[1002001];

void C(int p){
	lb = 0, ub = fact;
	while(ub - lb > 0){
		int mid = (lb + ub) / 2;
		if(p > tars[mid]){
			lb = mid + 1;
		} else if(p < tars[mid]){
			ub = mid;
		} else {
			break;
		}
	}
}

int main(){
	while(scanf("%d %d", &n, &m), n || m){
		ans = 0;
		k = 0;
		target[0] = 0;
		for(int i = 1; i <= n; i++){
			scanf("%d", &target[i]);
		}
		for(int i = 0;i <= n; i++){
			for(int j = 0; j <= n; j++){
				tars[k++] = target[i] + target[j];
			}
		}
		fact = (n + 1) * (n + 1);
		sort(tars, tars + fact);
		for(int i = 0; i <= fact; i++){
			if(tars[i] > m) continue;
			C(m - tars[i]);
			ans = max(ans, tars[i] + tars[ub - 1]);
		}
		printf("%d\n", ans);
	}
	return (0);
}