https://paiza.jp/poh/ec-campaign

gistfile1.py

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

import sys


class Solver(object):
    def __init__(self, items):
        self.nb_items = len(items)
        self.sorted_items = sorted(items)

    def solve(self, camps):
        return [self.solve_campaign(i) for i in camps]

    def solve_campaign(self, target_price):
        sorted_items = self.sorted_items

        left_cursor = 0
        right_cursor = self.nb_items - 1
        max_sum = 0

        while left_cursor < right_cursor:
            left_price = sorted_items[left_cursor]
            remain_price = target_price - left_price

            while left_cursor < right_cursor:
                right_price = sorted_items[right_cursor]
                if right_price <= remain_price:
                    max_sum = max(max_sum, left_price + right_price)
                    break
                right_cursor -= 1

            while left_cursor < right_cursor:
                left_cursor += 1
                if sorted_items[left_cursor] != left_price:
                    break

        return max_sum


def read_data_model_stream(st):
    (nb_items, nb_camps) = (int(i) for i in st.readline().split(' '))
    items = [int(st.readline()) for i in range(nb_items)]
    camps = [int(st.readline()) for i in range(nb_camps)]
    return items, camps


if __name__ == '__main__':
    items, camps = read_data_model_stream(sys.stdin)
    s = Solver(items)
    results = s.solve(camps)
    for pair_price in results:
        print pair_price