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); }