QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#137498 | #2354. Ook | Rd_rainydays# | WA | 2ms | 7844kb | C++20 | 1.8kb | 2023-08-10 13:30:07 | 2023-08-10 13:30:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=(a),i##_end_=(b);i<i##_end_;++i)
static const int M=250003;
int o,k,Fa[M];
char S[M],P[M];
int Nxt[M],n,m;
int Sum[M],Val[M];
int GetFa(int x){return Fa[x]==x?x:Fa[x]=GetFa(Fa[x]);}
vector<int>QO,QK;
int F[M];
int main(){
scanf("%d%d",&o,&k);
scanf("%s%s",S+1,P);
n=strlen(S+1);int op=n+1,kp=n+1;
m=strlen(P);
REP(i,1,n+1)
if(S[i]=='o')QO.push_back(i);
else QK.push_back(i);
for(int i=n;i>=1;--i){
if(S[i]=='o')Nxt[i]=op,op=i;
else Nxt[i]=kp,kp=i;
}
REP(i,1,n+1){
Sum[i]=Sum[i-1]+(S[i]=='o'?o:k);
Fa[i]=i;
}
REP(i,1,n-m+2)
Val[i]=Sum[i+m-1]-Sum[i-1];
//REP(i,1,n-m+2)cout<<Sum[i]<<' ';cout<<endl;
REP(i,0,strlen(P)){
if(P[i]=='?')continue;
int p;
//if(P[i]=='k'){
REP(j,i+1,n+1)if(S[j]!=P[i]){
if(j-i>n-m+1)break;
if(!(Val[j-i]>>=1))
Fa[j-i]=j-i+1;
j=GetFa(j);
}
/*
p=lower_bound(QO.begin(),QO.end(),i+1)-QO.begin();
int pe=QO.size();
while(p<pe){
if(QO[p]-i>n-m+1)break;
if(!(Val[QO[p]-i]>>=1))
Fa[QO[p]-i]=QO[p]-i+1;
p=max(p+1,(int)(lower_bound(QO.begin(),QO.end(),GetFa(QO[p]-i)+i+1)-QO.begin()));
}*/
//}
//else{
/*
p=lower_bound(QK.begin(),QK.end(),i+1)-QK.begin();
int pe=QK.size();
while(p<pe){
if(QK[p]-i>n-m+1)break;
if(!(Val[QK[p]-i]>>=1))
Fa[QK[p]-i]=QK[p]-i+1;
p=max(p+1,(int)(lower_bound(QK.begin(),QK.end(),GetFa(QK[p]-i)+i+1)-QK.begin()));
}*/
//}
}
REP(i,1,n+2){
if(i<=n-m+1)
F[i+m]=max(F[i+m],F[i]+Val[i]);
F[i]=max(F[i],F[i-1]);
}
printf("%d\n",F[n+1]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5780kb
input:
2 1 ookookook koo
output:
10
result:
ok single line: '10'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5780kb
input:
1 3 koooooook ?
output:
13
result:
ok single line: '13'
Test #3:
score: 0
Accepted
time: 2ms
memory: 7724kb
input:
1000 0 kookoo ook
output:
2000
result:
ok single line: '2000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 7692kb
input:
21 1 ooo kkk
output:
7
result:
ok single line: '7'
Test #5:
score: 0
Accepted
time: 2ms
memory: 7844kb
input:
1 0 ookko k??ko
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 2ms
memory: 5728kb
input:
5 8 koookokkok oo
output:
32
result:
ok single line: '32'
Test #7:
score: 0
Accepted
time: 2ms
memory: 7744kb
input:
12 13 kkokoookokkooko ?ooo??ook?k?
output:
18
result:
ok single line: '18'
Test #8:
score: 0
Accepted
time: 0ms
memory: 5776kb
input:
8 9 kkkkkkkkokkkokkokkok o????k???oo?o
output:
28
result:
ok single line: '28'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5724kb
input:
2 11 kkkoooooooookkookookokooo kkkokkkok?ok??okok
output:
1
result:
ok single line: '1'
Test #10:
score: -100
Wrong Answer
time: 2ms
memory: 7752kb
input:
0 14 kkookookkkokkkokkoooookokkkokk oooo?kooo?k
output:
15
result:
wrong answer 1st lines differ - expected: '22', found: '15'