UCC Coding Competition '21 P2 - Emerald Exchange

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

You are walking along the street when a street vendor offers you a special deal. He has a row of N emeralds with different sizes. Each emerald has an integer weight between 1 and 100, inclusive, and the weights are clearly labelled for each emerald. However, the vendor tells you that you should not touch or buy the emeralds with odd-numbered weights as they have dangerous magical properties.

The vendor offers you to buy any number of consecutive emeralds from his row, as long as that selection of emeralds does not include any odd-weighted emeralds.

What is the largest total weight of emeralds you can buy with one purchase, following the rule above?

Input Specification

The input will consist of two lines. The first line contains N, the number of emeralds in the vendor's row. The second line contains N space-separated integers between 1 and 100 inclusive, the weight of each emerald in the order that the vendor has them on display.

Output Specification

Please output one integer: the maximum possible sum of the weights of the emeralds that can be purchased as described above.

Constraints and Partial Marks

For 5 of the 10 available marks, 1 \le N \le 3000.

For the remaining 5 marks, 1 \le N \le 10^5.

Sample Input

2 3 4 4 5 6 1 2 2 2 1 8 2

Sample Output


Explanation of Sample Output

Buying the two rightmost emeralds, with sizes 8 and 2 (sum = 10), is the optimal purchase.

There are many suboptimal alternative purchases. These include:

  • Buying the three consecutive emeralds with size 2 (sum = 6),
  • Buying two of the three consecutive emeralds with size 2 (sum = 4),
  • Buying the two consecutive emeralds with size 4 (sum = 8), or
  • Buying a single emerald of size 2, 4, 6, or 8.


There are no comments at the moment.