https://paiza.jp/poh/ec-campaign の問題Python 2.7版。Java版のときの懸念である二分探索を使うことで速度改善。http://paiza.jp/poh/ec-campaign/result/614650f5d4cc71286f8cdfb3807029ef

paiza1.py

# -*- coding: utf-8 -*-
# Python 2.7.x用。 3.xで動かす場合は、raw_input()をinput()に変えればOK
 
import bisect
 
patterns = raw_input().split(' ')
product_num = int(patterns[0])
campaign_num = int(patterns[1])
 
product_prices = []
for _ in range(product_num):
    product_prices.append(int(raw_input()))
 
campaign_prices = []
for __ in range(campaign_num):
    campaign_prices.append(int(raw_input()))
 
product_prices.sort()
 
for campaign_price in campaign_prices:
    range_max = bisect.bisect_left(product_prices, campaign_price)
    max_price = 0
 
    for i in range(range_max - 1, 0, -1):
        remain_price = campaign_price - product_prices[i]
        index = bisect.bisect_left(product_prices, remain_price, 0, i - 1)
        price = product_prices[index] + product_prices[i]
        # 金額がcampaign_priceを超す場合は探索結果の1コ前の金額を使うこと
        # bisectが、「ソートされた順序を保ったまま x を a に挿入できる点を探し当てます。」のため、
        # 下記例の場合に200と500の間に値を入れる→すなわち2を返す動きのため。
        # >>> a = [100, 200, 500, 700, 800]
        # >>> bisect.bisect_left(a, 300)
        # 2
        if price > campaign_price:
            price = product_prices[index - 1] + product_prices[i]
 
        if price == campaign_price:
            max_price = price
            break
        elif max_price < price < campaign_price:
            max_price = price
    print(max_price)