ANARC05B - The Double HeLiX

Two finite, 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:

  1. You may start at the beginning of any of the two sequences. Now start moving forward.
  2. 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 finding 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 specified on two separate lines. Each line denotes a sequence and is specified 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

Added by:psetter
Date:2009-07-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ANARC 2005

hide comments
2015-06-23 19:20:02 Liquid_Science
There are multiple space b/w no. in test cases,beware.
Was getting nzec due to that :(

i.e. If you use split()

Last edit: 2015-06-23 19:22:15
2015-06-13 12:40:07 aryana
<snip>
getting wrong ans.why?


Last edit: 2023-05-28 23:05:28
2015-06-11 19:22:10 SHRINIKET ACHARYA
dont know why getting WA. passed all cases given in comments
<snip>

Last edit: 2023-05-28 23:05:35
2015-06-08 11:13:22 Pramod
the values of test cases are >10000 so check it once it lease me 2 more SIGSEV errors..
2015-06-02 21:51:06 Arjun Verma
Binary search + greedy + implementation
2015-06-01 19:43:23 [Mayank Pratap]
First think greedy ....and then hash it... :)
2015-05-29 19:17:46 Krishna Chouhan
used "long long int" everywhere and it got accepted.
here are some test cases.(test cases are included from prev. comments as well)
4 1 2 3 4
4 5 6 7 8
4 1 2 3 4
3 3 7 10
4 -30 -20 -10 10
4 -100 -80 -60 -30
6 1 2 4 6 8 20
6 22 24 26 28 30 40
6 1 4 8 20 100 500
1 1
6 1 4 8 20 100 500
1 1000
6 1 4 8 20 100 500
4 2 3 8 15
6 1 4 8 20 100 500
4 2 6 400 500
6 1 4 8 20 100 500
6 1 4 8 20 100 500
6 1 4 8 20 100 500
4 2 8 20 200
6 1 4 8 20 100 500
4 2 3 80 500
6 100 200 300 400 500 600
4 40 81 99 100
26
23
-30
170
633
1000
633
908
633
633
633
2320

2015-05-28 16:19:26 Shubham Bansal
just traversal can do it easily. O(n)
use long long instead of int
2015-03-24 19:42:16 Prince Raj Kumar
simple problem , no binary search, simple dp O(n) solution
2015-03-09 03:11:52 blaz1ngra1n
AC using O(N log N) with dynamic programming and binary search, although I know of a few other elegant solutions to this problem. Very nice problem overall; it's great for introducing DP.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.