ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#159116 | #228. book | hiapollo | 100 | 65ms | 13212kb | C++ | 1.3kb | 2022-09-21 14:39:51 | 2022-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'