QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#332995 | #6366. Message | xcyyyyy | WA | 3ms | 102244kb | C++14 | 2.8kb | 2024-02-19 16:47:16 | 2024-02-19 16:47:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define SN 200005
int N,n,m,c[SN];
char s[SN],t[SN];
int num;
int vis[200];
pair<int,int> x[60];
unsigned int C;int nxt[SN],S[SN],T[SN],lc[SN],lst[SN];
ll f[SN][60],pre[SN];
int main(){
srand(time(0));
scanf("%s%s",s+1,t+1);N=strlen(s+1),m=strlen(t+1);
for(int i=1;i<=N;i++)scanf("%d",&c[i]);
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++)if(!vis[t[i]])vis[t[i]]=1,x[++num]={i,t[i]};
memset(vis,0,sizeof(vis));
for(int i=m;i;i--)if(!vis[t[i]])vis[t[i]]=1,x[++num]={i,t[i]};
sort(x+1,x+1+num);num=unique(x+1,x+1+num)-x-1;
memset(f,-0x3f,sizeof(f));
for(int i=0;i<=N;i++)f[i][0]=0;
x[num+1].first=m+1;
for(int j=1;j<=num;j++){
//printf("%d %c\n",x[j].first,x[j].second);
n=m=C=0;
for(int i=0;i<26;i++){
bool f=false,g=false;
for(int k=1;k<=j;k++)f|=x[k].second==i+'a';
for(int k=j+1;k<=num;k++)g|=x[k].second==i+'a';
C|=(f&&g)<<i;
}
for(int i=x[j].first+1;i<x[j+1].first;i++)T[++m]=t[i];T[m+1]='\0';
for(int i=1;i<=N;i++)if(C>>(s[i]-'a')&1)S[++n]=s[i],lc[n]=i,pre[n]=c[i]+pre[n-1];
//puts("S");
//for(int i=1;i<=n;i++)cout<<(char)S[i];puts("");
//puts("T");
//for(int i=1;i<=m;i++)cout<<(char)T[i];puts("");
if(m==0){
f[0][j-1]=-0x3f3f3f3f3f3f3f3f;
for(int i=1;i<=N;i++)if(s[i]==x[j].second)f[i][j]=f[i-1][j-1]+c[i];
for(int i=1;i<=N;i++)if((~C>>(s[i]-'a')&1))f[i][j]=max(f[i][j],f[i-1][j]);
}else{
f[0][j-1]=-0x3f3f3f3f3f3f3f3f;
for(int i=N;i;i--)if(s[i]==x[j].second)f[i][j-1]=f[i-1][j-1]+c[i];else f[i][j-1]=-0x3f3f3f3f3f3f3f3f;
for(int i=1;i<=N;i++)if(~C>>(s[i]-'a')&1)f[i][j-1]=max(f[i-1][j-1],f[i][j-1]);
for(int i=2,j=0;i<=n;nxt[i++]=j+=(T[j+1]==T[i]))
while(j&&T[j]!=T[i])j=nxt[j];
for(int i=1,k=0;i<=n;i++){
while(k&&T[k+1]!=S[i])k=nxt[k];
k+=T[k+1]==S[i];
if(k==m){
//printf("%d -> %d\n",lc[i-m+1]-1,lc[i]);
f[lc[i]][j]=max(f[lc[i]][j],f[lc[i-m+1]-1][j-1]+pre[i]-pre[i-m]);
}
}
for(int i=1;i<=N;i++)if(~C>>(s[i]-'a')&1)f[i][j]=max(f[i-1][j],f[i][j]);
}
//for(int i=1;i<=N;i++)if(f[i][j]>=0)printf("%d(%lld) ",i,f[i][j]);puts("");puts("-=-=-=-=-=-=-=-=-");
}
if(f[N][num]<0)return puts("You better start from scratch man..."),0;
f[N][num]=-f[N][num];
for(int i=1;i<=N;i++)f[N][num]+=c[i];
printf("%lld\n",f[N][num]);
}/*
ca*b*****ccbbbc
946170804186214
ca*bcb**b*c**bc
acbcbb
3(6)
5(13)
6(13)
8(14)
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 102244kb
input:
ababccb abc 7 2 2 4 3 2 1
output:
12
result:
wrong answer 1st lines differ - expected: '7', found: '12'