• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
64%
SHARE
TWEET

# Subsequence Weighting solution

vbuterin Jan 9th, 2012 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. cases = int(raw_input())
2. for i in range(cases):
3.   numlen = int(raw_input())
4.   ints = [int(x) for x in raw_input().split(' ')]
5.   weights = [int(x) for x in raw_input().split(' ')]
6.   # Array of pairs of integers and the total score that can be attained going up to that
7.   # integer - eg. given pairs [1,10],[2,20],[3,30],[4,40],[1,15],[2,15],[3,15],[4,50]
8.   # we would have in this array [1,10] (and [1,15] eventually), [2,30], [3,60], etc
9.   inttoscore = [[0,0]]
10.   for i in range(len(ints)):
11.     # Binary search our way to the weight
12.     left,right = 0,len(inttoscore)-1
13.     while right-left > 1:
14.       ave = int((left+right)/2)
15.       if ints[i] > inttoscore[ave][0]: left = ave
16.       else: right = ave
17.     if ints[i] < inttoscore[left][0]: place = left
18.     elif ints[i] < inttoscore[right][0]: place = right
19.     else: place = right + 1
20.     while place > 0 and ints[i] == inttoscore[place-1][0]:
21.       place -= 1
22.     inttoscore.insert(place,[ints[i],weights[i] + inttoscore[place-1][1]])
23.     while place+1 < len(inttoscore) and inttoscore[place][1] >= inttoscore[place+1][1]: inttoscore.pop(place+1)
24.   #print ints, weights, scores
25.   print inttoscore[-1][1]
RAW Paste Data
Top