UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#159116#228. bookhiapollo10065ms13212kbC++1.3kb2022-09-21 14:39:512022-09-21 14:39:52

answer

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define LL long long
int que[2000020],seq[2000020],mn[1000010];
char opt[1000002];
inline LL abs(LL a){
    return a>0?a:-a;
}
inline LL max(LL a,LL b){
    return a>b?a:b;
}
inline LL min(LL a,LL b){
    return a<b?a:b;
}
int main(){
    LL n,p,q,x,y;
    int i,h,t;
    scanf("%lld %lld %lld %lld %lld",&n,&p,&q,&x,&y);
    scanf("%s",opt+1);
    for(i=n<<1;i>n;--i)seq[i]=seq[i+1]+(opt[i-n]=='+'?1:-1);
    for(i=n;i;--i)seq[i]=seq[i+1]+(opt[i]=='+'?1:-1);
    que[0]=0;
    h=1,t=0;
    for(i=n<<1;i;--i){
        while(h<=t&&seq[i]>seq[que[t]])--t;//seq[i]-seq[que[h]]>seq[que[t]]-seq[que[h]]
        que[++t]=i;
        while(h<=t&&que[h]-i>=n)++h;
        if(i<=n)mn[i]=seq[i]-seq[que[h]]; //你不能用head更新min,只能倒序用i
    }
    LL all=seq[n+1],tmp=(q-p-all)/2,ans=1e16,cst;
    for(i=0;i<n;i++){//枚举起点与枚举旋转次数不同
        cst=x*abs(tmp)+y*(LL)i;
        if(i==0){
            mn[1]+=p+max(tmp,0)*2;
            if(mn[1]<0)cst+=2*x*((1-mn[1])/2);
        }else{
            mn[n-i+1]+=p+max(tmp,0)*2;
            if(mn[n-i+1]<0)cst+=2*x*((1-mn[n-i+1])/2);
        }
        ans=min(ans,cst);
    }
    printf("%lld",ans);
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 520kb

input:

100 2 28 9426 9827
----+--+-++++-+++--+---+++------+---------++----+-++++-+--+++-++++++-+-+--+++--++...

output:

179094

result:

ok single line: '179094'

Test #2:

score: 10
Accepted
time: 0ms
memory: 516kb

input:

100 6 68 8136 6688
+++-+---+----+--+-++--+---++++++--+-++-++--+--++--+-++---+++-+++---++++-+++-+++++...

output:

219672

result:

ok single line: '219672'

Test #3:

score: 10
Accepted
time: 0ms
memory: 524kb

input:

100 4 0 7368 5364
-+-++---+--+-+-+-++++++++-+-++++--+-+---++---++--+++----+--+-----------+--+--+++--...

output:

36840

result:

ok single line: '36840'

Test #4:

score: 10
Accepted
time: 0ms
memory: 544kb

input:

1000 454 0 10 10000000
--+++++-+---++-++-+-++++-+--+---++++++++-+-++-+-+-+--+++--+----+--++++-++---+...

output:

2150

result:

ok single line: '2150'

Test #5:

score: 10
Accepted
time: 0ms
memory: 532kb

input:

1000 376 1144 440675445 812725011
++++-+------++---++---+--+++---++++--++--+-++++-+---++++-+++-+-+--...

output:

158643160200

result:

ok single line: '158643160200'

Test #6:

score: 10
Accepted
time: 3ms
memory: 536kb

input:

1000 276 18 938498793 701159019
-+++---+++-+---+++---+-+----+++-+-+-++---+--+++++-+---+-++-+----++++...

output:

95726876886

result:

ok single line: '95726876886'

Test #7:

score: 10
Accepted
time: 0ms
memory: 1796kb

input:

100000 67360 94034 10 10000000
---+++-++-+++---+-+--+-+------+-+---+----+----+-----+-+--+----+++-+--...

output:

131900

result:

ok single line: '131900'

Test #8:

score: 10
Accepted
time: 4ms
memory: 1796kb

input:

100000 57247 91 752278539 881719015
-+++++--+--++---+-----++-+-+++++-+-+--+-----++--+++++-+--+-+++-+...

output:

21465515831826

result:

ok single line: '21465515831826'

Test #9:

score: 10
Accepted
time: 26ms
memory: 13208kb

input:

1000000 897028 186010 944612613 866641998
+---+-++++--+---+---+----++--+-+---++---+-+++++++--+++-+--...

output:

335957143489128

result:

ok single line: '335957143489128'

Test #10:

score: 10
Accepted
time: 32ms
memory: 13212kb

input:

1000000 524180 1009530 659936979 574325878
++---++--+-++-+---+---+-++--+-++--+----++---+-++-+-+-++-+...

output:

159568801900326

result:

ok single line: '159568801900326'