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