ANARC05B  The Double HeLiX
Two ﬁnite, strictly increasing, integer sequences are given. Any common integer between the two sequences constitute an intersection point. Take for example the following two sequences where intersection points are
printed in bold:
 First= 3 5 7 9 20 25 30 40 55 56 57 60 62
 Second= 1 4 7 11 14 25 44 47 55 57 100
You can ‘walk” over these two sequences in the following way:
 You may start at the beginning of any of the two sequences. Now start moving forward.
 At each intersection point, you have the choice of either continuing with the same sequence you’re currently on, or switching to the other sequence.
The objective is ﬁnding a path that produces the maximum sum of data you walked over. In the above example, the largest possible sum is 450, which is the result of adding 3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, and 62
Input
Your program will be tested on a number of test cases. Each test case will be speciﬁed on two separate lines. Each line denotes a sequence and is speciﬁed using the following format:
n v1 v2 ... vn
Where n is the length of the sequence and vi is the ith element in that sequence. Each sequence will have at least one element but no more than 10,000. All elements are between 10,000 and 10,000 (inclusive).
The last line of the input includes a single zero, which is not part of the test cases.
Output
For each test case, write on a separate line, the largest possible sum that can be produced.
Sample
Input: 13 3 5 7 9 20 25 30 40 55 56 57 60 62 11 1 4 7 11 14 25 44 47 55 57 100 4 5 100 1000 1005 3 12 1000 1001 0 Output: 450 2100
hide comments
arafat_123:
20210319 20:06:42
Easy Problem!!! Don't get afraid by seeing the tags. You don't need to use them. AC in one go. 

jajopi:
20210318 20:44:06
Hi, I keep getting NZEC in Python 3, even though in my IDLE (3.7) runns literally all right cases from this discussion correctly and terminates just after the single 0. It also works on ideone.


rachit_agr:
20210301 08:24:12
Why it is giving NZEC in java ?? 

bks_7:
20201220 17:28:38
is there any concept in solving using dp and binarysearch?


priyanshux123:
20201103 13:01:00
If u don't wan't to use dp+binarysearch then it's simple using prefix sum 

distructo:
20200925 17:13:53
While switching to another array make sure to get the index of that common element in the 2nd array...if you are using dp+binary search 

luismbaezco:
20200910 04:54:43
O(N*log(N)) Using DP (Top Down) + lower_bound (Binary Search), but it takes a long time to think 

mega4411:
20200827 07:44:17
don't think about dp or binary search 

rehank478:
20200805 07:01:18
I think it's greedy problem. 

jopdhiwaala:
20200722 17:48:22
Made a mistake you can have not intersection points as well. 
Added by:  ~!(*(@*!@^& 
Date:  20090705 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ANARC 2005 