You have N cakes numbered from 0 to N - 1. You are given the following:
You have an array A of length N, where A[i] denotes the type of the ith cake.
You have an array B of length N, where B[i] denotes the happiness value of the ith cake.
Each time you eat a cake, the happiness value of it gets added to your total happiness.
There's also another factor determining the happiness you get:
Let the last two cakes eaten by you be of type T1 and T2 respectively (Note: T1 may be equal to T2 type, you will get double happiness value of the cake if T1 and T2 are equal).
If the next cake you eat is either of type T1 and T2, you get double happiness value of it.
You start eating cakes starting from cake one by one. Also, every time you eat a cake or skip eating it
you can get a cake one by one.
Task
Determine the maximum possible total happiness you can get by eating the cakes optimally.
Note: 0-based indexing is used.
Example 1:
Input:[3,[1,2,1],[5,5,4]]
Output:18
Example 2:
Input:[2,[1,2],[5,5]]
Output:15
Constraints:
1 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^5
1 ≤ B[i] ≤ 10^5
The sum of N over all testcases does not exceed 2 * 10^5
solution.cpp
Loading...
Run code to see test results
00:00 / 69:42
Tasty cakes
MediumMed•1,075 views
You have N cakes numbered from 0 to N - 1. You are given the following:
You have an array A of length N, where A[i] denotes the type of the ith cake.
You have an array B of length N, where B[i] denotes the happiness value of the ith cake.
Each time you eat a cake, the happiness value of it gets added to your total happiness.
There's also another factor determining the happiness you get:
Let the last two cakes eaten by you be of type T1 and T2 respectively (Note: T1 may be equal to T2 type, you will get double happiness value of the cake if T1 and T2 are equal).
If the next cake you eat is either of type T1 and T2, you get double happiness value of it.
You start eating cakes starting from cake one by one. Also, every time you eat a cake or skip eating it
you can get a cake one by one.
Task
Determine the maximum possible total happiness you can get by eating the cakes optimally.
Note: 0-based indexing is used.
Example 1:
Input:[3,[1,2,1],[5,5,4]]
Output:18
Example 2:
Input:[2,[1,2],[5,5]]
Output:15
Constraints:
1 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^5
1 ≤ B[i] ≤ 10^5
The sum of N over all testcases does not exceed 2 * 10^5