GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Monday 10 October 2022

[Solution] Swap and Take Codeforces Solution



E. Swap and Take
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You're given an array consisting of n integers. You have to perform n turns.

Initially your score is 0.

On the i-th turn, you are allowed to leave the array as it is or swap any one pair of 2 adjacent elements in the array and change exactly one of them to 0(and leave the value of other element unchanged) after swapping. In either case(whether you swap or not), after this you add ai to your score.

What's the maximum possible score you can get?

Input

The first line contains a single integer n (2n500).

The second line contains n integers a1,a2,,an (1ai106).

Output

Print a single integer — the maximum possible score.

Note

In the first example, to get the maximum score we do as follows. Do nothing on the first turn, add 3 to the score. Swap the first and the second elements and turn 1 to 0 on the second turn, and add 3 to the score. The final score is 6


No comments:

Post a Comment