Codeforces 355C Vasya and Robot【贪心+前缀和】

C. Vasya and Robottime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Vasya has n items lying in a line. The items are consecutively numbered by numbers from1 to n in such a way that the leftmost item has number1, the rightmost item has number n. Each item has a weight, the i-th item weightsw_i kilograms.

Vasya needs to collect all these items, however he won't do it by himself. He uses his brand new robot. The robot has two different arms — the left one and the right one. The robot can consecutively perform the following actions:

1. Take the leftmost item with the left hand and spend w_i · l energy units (w_i is a weight of the leftmost item, l is some parameter). If the previous action was the same (left-hand), then the robot spends extraQ_l energy units;
2. Take the rightmost item with the right hand and spend w_j · r energy units (w_j is a weight of the rightmost item,r is some parameter). If the previous action was the same (right-hand), then the robot spends extraQ_r energy units;

Naturally, Vasya wants to program the robot in a way that the robot spends as little energy as possible. He asked you to solve this problem. Your task is to find the minimum number of energy units robot spends to collect all items.

Input

The first line contains five integers n, l, r, Q_l, Q_r(1 ≤ n ≤ 10⁵; 1 ≤ l, r ≤ 100; 1 ≤ Q_l, Q_r ≤ 10⁴).

The second line contains n integers w₁, w₂, ..., w_n(1 ≤ w_i ≤ 100).

Output

In the single line print a single number — the answer to the problem.

ExamplesInput

3 4 4 19 1
42 3 99

Output

576

Input

4 7 2 3 9
1 2 3 4

Output

34

Note

Consider the first sample. As l = r, we can take an item in turns: first from the left side, then from the right one and last item from the left. In total the robot spends4·42 + 4·99 + 4·3 = 576 energy units.

The second sample. The optimal solution is to take one item from the right, then one item from the left and two items from the right. In total the robot spends(2·4) + (7·1) + (2·3) + (2·2 + 9) = 34 energy units.

题目大意：

给你N个数，每次操作只能拿最左边的数或者是最右边的数，拿最左边的数的时候花费价值为l*ai.拿最右边的数的时候花费价值为r*ai.

连续两次左操作要额外花费Ql价值，同理，连续两次右操作要额外花费Qr价值。

想要将所有元素都拿走，那么需要最小花费是多少。

思路：

O（n）枚举一个中间点，能够确定左边所有元素都是从左边拿取的，右边所有元素都是从右边拿取的。

那么如果没有额外花费这个问题，我们只要维护一个前缀和以及一个后缀和即可。

现在有额外花费这个问题，加以一点点贪心思想就解决了：

既然如果两次左操作需要额外花费Ql，那么我们肯定希望两种操作穿插着进行。

那么如果假设此时L个左元素，以及R个右元素，那么如果有：Abs（L-R）<=1,那么肯定就可以做到没有额外花费。

相反，如果有Abs（L-R）>1，再讨论一下L大还是R大，就能够确定最多进行多少次额外的操作了。

Ac代码：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
int a[108000];
int sum[108000];
int back[108000];
int main()
{
    int n,l,r,ql,qr;
    while(~scanf("%d%d%d%d%d",&n,&l,&r,&ql,&qr))
    {
        memset(back,0,sizeof(back));
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        for(int i=n;i>=1;i--)
        {
            back[i]=back[i+1]+a[i];
        }
        int output=INT_MAX;
        for(int i=0;i<=n;i++)
        {
            int left=i;
            int right=i+1;
            int tmpsum=sum[left]*l+back[right]*r;
            int contleft=i;
            int contright=n-i;
            if(abs(contleft-contright)>1)
            {
                if(contleft>contright)
                {
                    tmpsum+=(contleft-contright-1)*ql;
                }
                if(contleft<contright)
                {
                    tmpsum+=(contright-contleft-1)*qr;
                }
            }
            output=min(output,tmpsum);
        }
        printf("%d\n",output);
    }
}