https://paiza.jp/poh/ec-campaign への回答

ec_campaign.py

# -*- coding: utf-8 -*-

try:
	import bisect
except:
	pass

def main():
	(num_items, num_days) = map(int, raw_input().split())
	prices = sorted(int(raw_input()) for n in xrange(num_items))
	goals  = (int(raw_input()) for n in xrange(num_days))

	for goal in goals:
		print find_closest(goal, prices)

def find_closest(goal, prices):
	closest = 0
	maximum = prices[-1]

	first_prices = slice_prices(prices, max_price = goal)
	for first_price in first_prices:
		if first_price + maximum < closest:
			break

		second_price = find_second_price(prices, max_price = goal - first_price, except_once = first_price)
		if second_price:
			current_price = first_price + second_price
			if current_price == goal:
				return goal
			elif current_price > closest:
				closest = current_price

	return closest

def slice_prices(prices, max_price):
	right = bisect.bisect_right(prices, max_price)
	for n in xrange(right - 1, -1, -1):
		yield prices[n]

def find_second_price(prices, max_price, except_once):
	for price in slice_prices(prices, max_price):
		if price == except_once:
			except_once = None
		else:
			return price

main()