2015年3月8日 星期日

2015/03/08 POI 15th BBB

/*
    貌似做了些 不必要的事=ㄦ=
    以後有好奇的人問(? 我在修掉好樂(欸
    
    很明顯的順序不重要
    於是枚舉說 轉幾此
    然後算出 最佳解這樣
*/
// http://main.edu.pl/en/archive/oi/15/bbb
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>

using namespace std;

typedef long long ll;

int N;
int p, q, x, y;

char c[3000000];
int A[3000000];
int pre[3000000];

int ask(int x)
{
    if( x == -1 ) return 0;
    else return pre[x];
}

int main()
{
    scanf("%d", &N);

    scanf("%d %d %d %d", &p, &q, &x, &y);
    scanf("%s", c);

    int t = 0;

    for(int Ni = 0; Ni < N; Ni++)
    {
        c[Ni+N] = c[Ni];
        t += c[Ni] == '+' ? 1 : -1 ;
    }

    pre[0] = c[0] == '+' ? 1 : -1 ;

    for(int Ni = 1; Ni < N*2; Ni++)
    {
        int d = c[Ni] == '+' ? 1 : -1 ;
        pre[Ni] = pre[Ni-1]+d;
    }

    int d = (q-p-t)/2;
    int Ans = abs(d)*x;

    if( d < 0 ) d = 0;

    int st = 0, ed = 0, cnt = 0;

    while( st < N )
    {
        while( ed < st || cnt < d )
        {
            if( c[ed++] == '-' ) cnt++;
        }

        A[st] = ed;

        if( c[st++] == '-' ) cnt--;
    }

    st = 0; ed = 0;

    deque<int> s;

    ll mn = 4e18;

    for(int Ni = 0; Ni < N; Ni++)
    {
        while( ed < Ni+N )
        {
            while( !s.empty() && ask(s.back() ) >= ask(ed) ) s.pop_back();
            s.push_back(ed++);
        }

        st = A[Ni];

        while( !s.empty() && s.front() < st ) s.pop_front();

        int t = ask(s.front() );

        ll z = (N-Ni)%N;

        ll e;

        if( t-ask(Ni-1)+p+d*2 >= 0 ) e = 0;
        else e = (t-ask(Ni-1)+p+d*2-1)/2;

        mn = min(mn, z*y+Ans-e*x*2);

    }

    printf("%lld\n", mn);
}

沒有留言:

張貼留言