Problem:


財宝 (Treasures)

問題

盗賊の Anna と Bruno は大富豪の邸宅に忍び込み，財宝 1 から財宝 N までの N 個の財宝を見つけた．これらの財宝を Anna と Bruno で分配することになった．財宝のうちのいくつかを Anna が取り，残りの財宝のうちのいくつかを Bruno が取る．同じ財宝を 2 人が取ることはできない．Anna や Bruno は財宝を 1 個も取らなくてもよい．また，残った財宝は邸宅に残しておくので，2 人とも取らない財宝があってもよい．

それぞれの財宝には「市場価値」と「貴重度」という 2 つの値が定まっている．Anna が取った財宝の市場価値の合計と Bruno が取った財宝の市場価値の合計の差の絶対値が D 以下なら，Anna は公平だと思って満足する．一方，Bruno は，Anna より貴重度の大きい財宝が欲しいと思っている．

Anna が満足するように財宝を分配したときの，Bruno が取った財宝の貴重度の合計から Anna が取った財宝の貴重度の合計を引いた値の最大値を求めよ．

入力

入力は 1 + N 行からなる．

1 行目には，2 つの整数 N, D (1 ≤ N ≤ 30，0 ≤ D ≤ 1015) が空白を区切りとして書かれている．これは，財宝の個数が N 個であり，Anna が取った財宝の市場価値の合計と Bruno が取った財宝の市場価値の合計の差の絶対値が D 以下なら Anna が満足することを表す．

続く N 行のうちの i 行目 (1 ≤ i ≤ N) には，2 つの整数 Xi, Yi (0 ≤ Xi ≤ 1015，0 ≤ Yi ≤ 1015) が空白を区切りとして書かれている．これは，財宝 i の市場価値が Xi であり，貴重度が Yi であることを表す．

与えられる 5 つの入力データのうち，入力 1 では N ≦ 10 を満たす．また，入力 2 では D = 0 を満たす．

出力

Anna が満足するように財宝を分配したときの，Bruno が取った財宝の貴重度の合計から Anna が取った財宝の貴重度の合計を引いた値の最大値を 1 行で出力せよ．

入出力例

  
入力例 1

  

6 15
50 900
30 200
40 100
80 600
60 100
70 700

   
出力例 1

   

1200

  
入力例 2

  

5 0
0 1000000000000000
0 1000000000000000
1 1
1000000000000000 0
1000000000000000 0

   
出力例 2

  

2000000000000000

入出力例 1 においては，Anna が財宝 2 と財宝 3 と財宝 5 を取り，Bruno が財宝 1 と財宝 6 を取ると，取った財宝の市場価値の合計は Anna が 130，Bruno が 120 となり，差の絶対値 10 が D = 15 以下なので Anna は満足する．このとき，取った財宝の貴重度の合計は Anna が 400，Bruno が 1600 となり，Bruno が取った財宝の貴重度の合計から Anna が取った財宝の貴重度の合計を引いた値は 1200 となる．これが最大である．

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
6 15
50 900
30 200
40 100
80 600
60 100
70 700


Sample output:
1200

Submission status: Time Limit Exceeded

Solution code:
#def get_mid(market, second_list):
    #right = len(second_list) - 1
    #left = 0
    #while left < right:
        #mid = right + left
        #if(market + second_list[mid][0] == -1 * D):
            #while market + second_list[mid][0] == -1 * D and mid >= 0:
                #mid -= 1
            #return mid
        #elif(market + second_list[mid][0] > -1 * D):
            #right = mid
        #else:
            #left = mid + 1
    #return right -1
def get_range(market, second_list):
    result = []
    for i in range(len(second_list)):
        if(abs(market + second_list[i][0]) <= D):
            result.append(i)
    return result

def make_enumration(in_list, out_list):
    length = len(out_list)
    for i in range(length):
        out_list.append(tuple([x + y for x, y in zip(out_list[i], in_list[0])]))    
        out_list.append(tuple([x - y for x, y in zip(out_list[i], in_list[0])]))
    
    if len(in_list) > 1:
        out_list = make_enumration(in_list[1:], out_list)
    return out_list
    
N, D = list(map(int, input().split()))
tre_list = []
for i in range(N):
    tre_list.append(tuple(map(int, input().split())))
    
first_list = make_enumration(tre_list[:int((N/2))], [(0, 0)])
second_list = make_enumration(tre_list[int((N/2)):], [(0, 0)])
second_list.sort(key=lambda treasure: treasure[0])
answer = 0

#length = len(second_list)
#for pattern in first_list:
    #if(pattern[0] < 0):
        #continue
    #if(pattern[0] + second_list[0][0] >= -1 * D):
        #start = 0
    #elif(pattern[0] + second_list[length -1][0] < -1 * D):
        #start = length
    #else:
        #start = get_mid(pattern[0],second_list)
    
    #while(start <= length -1 and pattern[0] + second_list[start][0] <= D):
        #if(answer < pattern[1] + second_list[start][1]):
            #answer = pattern[1] + second_list[start][1]
        #start += 1
for pattern in first_list:
    x_range = get_range(pattern[0], second_list)
    for i in x_range:
        if(answer < abs(pattern[1] + second_list[i][1])):
            answer = abs(pattern[1] + second_list[i][1])

print(answer)

Submission status: Runtime Error

Solution code:
#Some of grobal args
COMMANDS = ["Anna", "trush", "Bruno"]
MARKETSUM = 0
answer = 0

#List for rare, market value
tre_list = []

class Thieves():
    #This holds two thieves market and rare value.
    def __init__(self, parent=None):
        if parent is None:
            self.Anna = [0, 0]
            self.Bruno = [0, 0]
        else:
            self.Anna = parent.Anna
            self.Bruno = parent.Bruno

    def market_diff(self):
        return abs(self.Anna[0] - self.Bruno[0])
    
    def rare_diff(self):
        return abs(self.Anna[1] - self.Bruno[1])
    
    def add_treasure(self, commands, treasure):
        if commands == "Anna":
            self.Anna = [x + y for x, y in zip(self.Anna, treasure)]
        elif commands == "Bruno":
            self.Bruno = [x + y for x, y in zip(self.Bruno, treasure)]
            
        return True    
            
        
def rec_calc(index, thieves):
    #This calculate answer recursively
    if thieves.Anna[0] > (MARKETSUM + D) / 2 + 1:
        return True
    global answer
     
    offset = 2 if index == 0 else 3 

    #if necessaly, overwrite answer
    if (answer < thieves.rare_diff()) and (D >= thieves.market_diff()):
        answer = thieves.rare_diff()
        
    #recursively call
    if(index < N):
        for command in COMMANDS[:offset]:
            new_thieves = Thieves(thieves)
            new_thieves.add_treasure(command, tre_list[index])
            rec_calc(index + 1, new_thieves)



#start of main function
#Get input and sort list by market value
N, D = list(map(int, input().split()))
for i in range(N):
    tre_list.append(list(map(int, input().split())))
    
tre_list.sort(key=lambda treasure: treasure[0], reverse=True)

#calc sum of market_value
for i in tre_list:
    MARKETSUM += i[1]

#calc and print answer
thieves = Thieves()
rec_calc(0, thieves)

print(answer)