Limits 1s, 32 MB

In a bustling medieval town, Arwa stumbled upon a lively carnival, its tents and banners fluttering in the breeze. Amidst the crowd’s chatter and laughter, she spotted a peculiar stall adorned with colorful balloons and mysterious prizes. Curiosity piqued, she approached the stall, where a wizened carnival master awaited. “Welcome, fair maiden, to the Pop! Shop” he proclaimed, gesturing towards a row of NN balloons, each bearing its own enigmatic value, viv_i.

“In this grand spectacle, ye shall wield special darts, each endowed with magical properties.“, the carnival master explained, “With these darts, ye can perform daring feats to pop the balloons and earn points.” He continued, “Be wary maiden, you can leave a balloon untouched, but each balloon can be popped only once. And the more points ye amass, the grander the reward!”. With a twinkle in her eye, Arwa listened intently as the carnival master detailed the ways she could wield her dart:

  • The Single Shot: Arwa could aim her dart at a single balloon, popping it to earn its value viv_i;

  • The Double Strike: By targetting two adjacent balloons simultaneously - the ii-th and (i+1)(i+1) -th balloons - Arwa’s magical dart, when thrown, would unleash double darts popping the two balloons, earning the product of their values vi×vi+1v_i \times v_{i+1};

  • The Spectacular Sweep: Should Arwa choose, she could aim her magical dart in a way that hits two different ballons ii and j>i+1j > i +1, earning the value vi×vjv_i \times v_j. But she needs to keep two things in mind when using this move:

    1. Sweep on balloons ii and jj can be performed only if all balloons between them, from (i+1)(i + 1) to (j1)(j - 1), had been popped earlier.

    2. In case she decides to perform multiple sweeps, their ranges cannot be disjoint. Given Sweep 2 (involving balloons i2i_2 and j2j_2) is performed after Sweep 1 (involving balloons i1i_1 and j1j_1), Arwa needs to maintain i1>i2i_1 > i_2 and j1<j2j_1 < j_2. This should be followed for all subsequent cases of sweeps.

Eager to embark on this daring adventure, Arwa faced the challenge: given the number of balloons and their associated values, she sought to devise a strategy to maximize her score. With determination in her heart, Arwa pondered her options, ready to seize the opportunity and claim the greatest prize the carnival had to offer.


The first line of the input contains a single integer N(1N5000)N (1 \leq N \leq 5000) denoting the number of balloons.

The following line contains NN space-separated integers, vi(107vi107)v_i (-10^7 \leq v_i \leq 10^7) indicating the value associated with each balloon.


Print a single integer denoting the maximum score.


4 5 3

Arwa can use the Double Strike to pop the first two balloons getting 4×5=204 \times 5 = 20 points. Then she can use the Single Shot to pop the third balloon to get 33, totalling 2323 points.

9 5 15 20 13 17 30

Arwa can perform a Single Shot to get 55 and use the Double Strike to get 15×2015 \times 20. Then she can perform the Spectacular Sweep to get 9×139 \times 13 and finally use the Double Strike to get 17×3017 \times 30. Note that, if she were allowed to perform disjoint sweeps, she could get 5+9×15+13×17+20×30=9615 + 9 \times 15 + 13 \times 17 + 20 \times 30 = 961, but the carnival master will not allow it.


Login to submit.


50% Solution Ratio
Sarwar82Earliest, 2w ago
Sarwar82Fastest, 0.1s
Sarwar82Lightest, 5.2 MB
Talha76Shortest, 1119B
Toph uses cookies. By continuing you agree to our Cookie Policy.