QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#137550 | #2354. Ook | Rd_rainydays# | WA | 2ms | 7980kb | C++14 | 1.6kb | 2023-08-10 13:55:32 | 2023-08-10 13:56:06 |
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'){
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){
F[i]=max(F[i],F[i-1]);
if(i<=n-m+1)
F[i+m]=max(F[i+m],F[i]+Val[i]);
}
printf("%d\n",F[n+1]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5684kb
input:
2 1 ookookook koo
output:
10
result:
ok single line: '10'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7760kb
input:
1 3 koooooook ?
output:
13
result:
ok single line: '13'
Test #3:
score: 0
Accepted
time: 2ms
memory: 7744kb
input:
1000 0 kookoo ook
output:
2000
result:
ok single line: '2000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 7848kb
input:
21 1 ooo kkk
output:
7
result:
ok single line: '7'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5940kb
input:
1 0 ookko k??ko
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5684kb
input:
5 8 koookokkok oo
output:
32
result:
ok single line: '32'
Test #7:
score: 0
Accepted
time: 2ms
memory: 7980kb
input:
12 13 kkokoookokkooko ?ooo??ook?k?
output:
18
result:
ok single line: '18'
Test #8:
score: 0
Accepted
time: 0ms
memory: 7848kb
input:
8 9 kkkkkkkkokkkokkokkok o????k???oo?o
output:
28
result:
ok single line: '28'
Test #9:
score: -100
Wrong Answer
time: 1ms
memory: 5732kb
input:
2 11 kkkoooooooookkookookokooo kkkokkkok?ok??okok
output:
2
result:
wrong answer 1st lines differ - expected: '1', found: '2'