Willy Wonka and Candies
All submissions for this problem are available.
Willy Wonka has gone to collect berries for his candy. He finds a rather odd kind of bush with berries growing on the bush in a straight line.Willy also observed that the sweetness imparted by the berries to the candy produced depended on the berries he plucked.
He saw that the sweetness imparted by the berry he plucked would depend on whether the neighboring berry will also be plucked or not.
For example, if berries have indexes 1 2 3 4 5 , then selecting berry 3 will affect sweetness imparted by 2 and 4,
after this if 4 is selected sweetness imparted by 2 is not affected (but sweetness imparted by 5 changes as it should) but when 1 is selected sweetness imparted by 2 is again affected.
Willy was able to determine how much sweetness each berry could impart to the candy for each case.
1.If neither the left nor the right immediate neighbor is selected then the sweetness imparted is A.
2.If one of the left or right immediate neighbors is selected then sweetness imparted is B.
3.If both the immediate neighbors have been selected then sweetness imparted is C.
Though there is no relation between A,B,C of the berries.
Now Willy wants to decide which berries to select so that the sweetness of the candy formed is maximum.He does not need to use all berries.
Help Willy find the maximum sweetness he can gain from the berries.The berries cannot be moved around the bush and the sweetness is additive in nature, as in, if we add two berries total sweetness is sum of both the berries.
A test file may have several test cases. Each test case starts with N ( N ≤ 10^6 ) the number of berries on the bush.The next N lines contain description of berries. Each line contains three integers A ( 0 ≤ A ≤ 100 ) , B ( 0 ≤ B ≤ 100) and C ( 0 ≤ C ≤ 100) in this order, which represent the sweetness values of the ith berry.The input data will end with end of file.
The output should consist of one integer in one line for each test case which will be the maximum sweetness that can be obtained for that case.
Input 1: 1 1 2 3 Output: 1
Input 2: 2 1 2 3 2 2 1 Output: 4
As there is only one berry the berry can only have A as its sweetness.
Here there are two berries and the cases are
1. select only first : total=1 (A of first)
2. select only second : total=2 (A of second)
3. select both first and second : total= 2+2=4 (sum of B of both)
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions