QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300178 | #2413. Disposable Switches | C1942huangjiaxu | WA | 1ms | 9976kb | C++14 | 856b | 2024-01-07 19:43:18 | 2024-01-07 19:43:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
typedef long long ll;
int n,c,r,a[N],b[N],ct,pr[N],nx[N];
ll ans;
bool cmp(int x,int y){
return abs(a[x])<abs(a[y]);
}
void chg(int x,int y,int v){
if(!x||!y)return;
if((y-x&1)==(1ll*a[x]*a[y]>0))ct+=v;
}
int main(){
scanf("%d%d%d",&n,&c,&r);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
b[i]=i;
}
sort(b+1,b+n+1,cmp);
for(int i=1,ls=0;i<=n;++i){
if(!a[i]){
ans+=r;
continue;
}
if(ls&&1ll*a[i]*a[ls]>0)ans+=r;
pr[i]=ls,nx[ls]=i;
chg(ls,i,1);
ls=i;
}
ans=min(ans,1ll*ct*r+c);
for(int i=1;i<=n;++i)if(a[b[i]]){
int x=b[i];
chg(pr[x],x,-1);
chg(x,nx[x],-1);
if(pr[x])nx[pr[x]]=nx[x];
if(nx[x])pr[nx[x]]=pr[x];
chg(pr[x],nx[x],1);
ans=min(ans,1ll*abs(a[x])*c+c+1ll*ct*r);
}
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 9976kb
input:
10 10 8 3 288076531 2 7 989836507 5 9 888938245 5 3 798750744 4 10 577049818 4 8 668653513 8 2 625131349 4 1 297966354 3 6 390595513 5 4 742946519
output:
72
result:
wrong answer 1st lines differ - expected: '7', found: '72'