对拍1145组没过求助
查看原帖
对拍1145组没过求助
574338
Scene楼主2024/1/11 16:10
#include<bits/stdc++.h>
#define fo(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define Ts template<typename Ty,typename... Ar>
#define Tp template<typename Ty>
#define ll long long
#define RS register
#define gc getchar
#define pc putchar
#define I inline
using namespace std;
Tp I Ty wmax(Ty a,Ty b){return a>=b? a:b;}
Tp I Ty wmin(Ty a,Ty b){return a<=b? a:b;}
namespace WrongIO
{
	Tp I void read(Ty &x){x=0;Ty opt=1;char c=gc();while(!isdigit(c)&&c!='-')c=gc();if(c=='-')opt=-1,c=gc();while(isdigit(c))x=(x<<3)+(x<<1),x+=c-'0',c=gc();x*=opt;return;}
	Tp I void write(Ty x){short OI_USE[50],OI_top=0;if(x<=0) if(x==0)pc('0');else pc('-'),x*=-1;while(x)OI_USE[++OI_top]=x%10,x/=10;while(OI_top--)pc(OI_USE[OI_top+1]+'0');return;}
    I void writec(char c[]){int len=strlen(c);for(int i=0;i<len;i++)pc(c[i]);}
    I void writes(string s){int len=s.length();for(int i=0;i<len;i++)pc(s[i]);}
    I void readc(char &c,int l,int r){c=gc(); while(c!=EOF&&(c<l||c>r)) c=gc();}
    I void readc(char &c,char val){c=gc();while(c!=EOF&&c!=val) c=gc();}
    I void readc(char val){char c;c=gc();while(c!=EOF&&c!=val) c=gc();}
    I void readls(string &s){char c=gc();while(c!='\n') s.push_back(c),c=gc();}
    Ts I void read(Ty &x,Ar &...y) {read(x),read(y...);}
} using namespace WrongIO;
ll n,p,q,x,y;
ll e[2000050],s[2000050];
deque<ll> dq;
int main()
{
	//freopen("data.in","r",stdin);
	//freopen("my.out","w",stdout);
	read(n,p,q,x,y);
	for(ll i=1;i<=n;i++)
	{
		char c; readc(c,'+','-');
		e[i]=e[i+n]=(c=='-'? -1:1);
	}
	for(ll i=1;i<=2*n;i++) s[i]=s[i-1]+e[i];
	//for(ll i=n+1;i<=2*n;i++) s[i]-=s[i-n];
	ll cs=p+s[n]-q; cs/=2; cs=-cs;
	for(ll i=1;i<=n;i++)
	{
		while(!dq.empty()&&s[dq.back()]>s[i]) dq.pop_back();
		dq.push_back(i);
	}
	ll gx=abs(cs)*x+n*y,ans=1e9;
	if(cs<0) cs=0;
	for(ll i=n+1;i<=2*n;i++)
	{
		gx-=y;
		while(!dq.empty()&&i-dq.front()>n) dq.pop_front();
		while(!dq.empty()&&s[dq.back()]>s[i]) dq.pop_back();
		dq.push_back(i);
		ll nd=s[dq.front()]; nd+=p+cs*2-s[i-n];
		if(nd<0) ans=wmin(ans,gx+abs(nd)*2*x);
		else ans=wmin(ans,gx);	
	}
	write(ans);
	return 0;
}
2024/1/11 16:10
加载中...