QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#137575 | #2354. Ook | Rd_rainydays# | TL | 1147ms | 8460kb | C++14 | 1.7kb | 2023-08-10 13:59:50 | 2023-08-10 14:05:12 |
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;
}
/*
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: 0ms
memory: 7748kb
input:
2 1 ookookook koo
output:
10
result:
ok single line: '10'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7976kb
input:
1 3 koooooook ?
output:
13
result:
ok single line: '13'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5728kb
input:
1000 0 kookoo ook
output:
2000
result:
ok single line: '2000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 5688kb
input:
21 1 ooo kkk
output:
7
result:
ok single line: '7'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5804kb
input:
1 0 ookko k??ko
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 7744kb
input:
5 8 koookokkok oo
output:
32
result:
ok single line: '32'
Test #7:
score: 0
Accepted
time: 2ms
memory: 7768kb
input:
12 13 kkokoookokkooko ?ooo??ook?k?
output:
18
result:
ok single line: '18'
Test #8:
score: 0
Accepted
time: 0ms
memory: 5816kb
input:
8 9 kkkkkkkkokkkokkokkok o????k???oo?o
output:
28
result:
ok single line: '28'
Test #9:
score: 0
Accepted
time: 0ms
memory: 5708kb
input:
2 11 kkkoooooooookkookookokooo kkkokkkok?ok??okok
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 1ms
memory: 5812kb
input:
0 14 kkookookkkokkkokkoooookokkkokk oooo?kooo?k
output:
22
result:
ok single line: '22'
Test #11:
score: 0
Accepted
time: 2ms
memory: 7756kb
input:
30 4 oookooookkokkkookkkkkkookkokokkookk o?ko?ok
output:
251
result:
ok single line: '251'
Test #12:
score: 0
Accepted
time: 1ms
memory: 5956kb
input:
35 18 okookkoookookokkkokkkkkkkokoookookokkkoo okkk???o?kkkko?kko?kkok?o
output:
19
result:
ok single line: '19'
Test #13:
score: 0
Accepted
time: 1ms
memory: 7704kb
input:
28 0 kokkoookokoookooookokokkkkokkkookkkkoookkkoko o
output:
616
result:
ok single line: '616'
Test #14:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
22 1 oooookooookkokkokooooookokkokokookkokookkkkokokoko o?ooo?ok???o???oko?ok??oko
output:
40
result:
ok single line: '40'
Test #15:
score: 0
Accepted
time: 1ms
memory: 5720kb
input:
13 15 okkkoookkkokkooookkoookoookokkkokookokkkookkookoookokoo k??kk???kkoo?kk
output:
105
result:
ok single line: '105'
Test #16:
score: 0
Accepted
time: 1ms
memory: 7848kb
input:
13 46 okokokkkkkokokokokokkokkokkoookkooookokkkkookokkookkkokkooko ?oo??koko?okokk?k??kok????k?k?kk
output:
30
result:
ok single line: '30'
Test #17:
score: 0
Accepted
time: 0ms
memory: 5784kb
input:
2 59 okokoooookokkokkkookookkokkoookokookokkkoookkkokokokkookookkkokok ?ooo?kko?kk??ko?kokk?ook?oo??
output:
52
result:
ok single line: '52'
Test #18:
score: 0
Accepted
time: 0ms
memory: 7984kb
input:
11 10 kkkokokookookoooooooooookkooookkokokkookookokokkooookokkokokookokokkko okoooookko?kk?kkok?
output:
13
result:
ok single line: '13'
Test #19:
score: 0
Accepted
time: 0ms
memory: 7768kb
input:
56 63 kkokkokokkkookkoookkkkkkkkkkokoooookookokookoookkokkkkkkkookokkokkkookokokk k?k??
output:
3622
result:
ok single line: '3622'
Test #20:
score: 0
Accepted
time: 1ms
memory: 5664kb
input:
15 16 kkkkookkkkkkokokokookkoookkkkookkookkkokkkokoookokkokokokokoookokkkkokokokkookok ?o?kok?oo??kkooo??o???ko?k
output:
113
result:
ok single line: '113'
Test #21:
score: 0
Accepted
time: 2ms
memory: 7764kb
input:
82 12 kkkkookkokkkoookkkkokookookooookokoookooookokoookokooookkoookokoookkokkkokokokookokko kok??ooook?
output:
1380
result:
ok single line: '1380'
Test #22:
score: 0
Accepted
time: 1ms
memory: 7768kb
input:
86 53 okookokookokookookkokkkooooookkokokokkkkkookookkkkookokokkkkkokokkkokkookkkkokookokokkookk oo??kk?kkokokk???okk?o???ko
output:
286
result:
ok single line: '286'
Test #23:
score: 0
Accepted
time: 2ms
memory: 7816kb
input:
30 0 oookkokokkkkkookkkkokokkookkokkkokokkkokokkookokokkkoooookkookkkokokoookkookokookkokooookokoook oo?okk?ok?k?o?oo?k?ok??o?ko?o?
output:
40
result:
ok single line: '40'
Test #24:
score: 0
Accepted
time: 0ms
memory: 7748kb
input:
65 51 kkoookkoooookokookkokkokokooookkkoookookokkkkkoookoookokkookkokoooooookokkokkokkkkkokookookkkkooooko ?k?kko
output:
3020
result:
ok single line: '3020'
Test #25:
score: 0
Accepted
time: 1ms
memory: 5732kb
input:
139 158 koookookkkooookkokkkkkkokkokkoookooookkokkkkkkkookkookkkkkookkkkkkooookokkokkkokoookkokokoookkokookkkokoooookokooookookkkokkokkkkkkoookookkookkookoookoookkokkkokokokkkkookokkkkokkookoookokkokkkoookkok ook???kko??kok?oo?o??oo??kkkkk
output:
1053
result:
ok single line: '1053'
Test #26:
score: 0
Accepted
time: 1ms
memory: 5672kb
input:
49 236 oookoooookkokkokokkokokkkokokkokkkooookooookokkkokokkkkkoookokookookkkooookkkoookoooookookokokkokkkkkkkookkkkokokokokkkoookkookokoookokkokkkkoookoookookkoookookkokkoookkkookkkookookokkkkokokkkokkkoooooookokoookkkoookkkkkokkkkokkoooookokookokkokkkokkookkoooookkokokkkkkkkokokkkoookokkokkkoookkk...
output:
22936
result:
ok single line: '22936'
Test #27:
score: 0
Accepted
time: 1ms
memory: 5688kb
input:
352 395 kkookkokokookkokkokkkooooookkookkkkookkkkkkkkookookokookooookkkookkkkokkookkkkkookkokookkokkkkkkooooooookokokkookokkokkokkkokkkookoookkokokookkoookkkkooookkkkokkokkkkooookkokokooookkokokokookkokokkokookkkokkookkokoookookookokoookkkookkoookokkokooooooooooooookookookkkkookokokkkkookkkookokkooo...
output:
91919
result:
ok single line: '91919'
Test #28:
score: 0
Accepted
time: 0ms
memory: 5956kb
input:
318 17 kookkokkoooooooooookkookokooookookookookkkkokkkkkkkokkkkokkokkoookkookokokookokokokokokoookkkokkokkkokokookkoookkokokokkokkokookkkkoookokokokokokkokkoookkkkkkkkkkkokkookokoooooookkkkkkokkkkokokookokkkkokokokkookokokoookkokooookokkookkokoookoookkokkookokkokkkkkkookkokkkkkokkookookokkkokkkokokk...
output:
16537
result:
ok single line: '16537'
Test #29:
score: 0
Accepted
time: 2ms
memory: 7988kb
input:
1 581 ookkkkokokokkkoookokookkokkkooookkkoooookoookokkookooookkkkokkokookkooooookkoookkokokkkkkokokkoookokkkkkoookkkkkookkokkookkkokkookkkokokkoookokkokkkookookookookokooooookooookooookoookkokokkookkkokoooookkokkokkkkkkoooookkookokkkokokkkkkooooookokookkokkokkkkookookokkookkkkkokkokkkkokkkkkoooookkk...
output:
1673
result:
ok single line: '1673'
Test #30:
score: 0
Accepted
time: 1ms
memory: 5784kb
input:
166 482 ooooookkookkoookkkkokokokooookookokokokokokkkkkkkkkookkookkkkokkkkkkookkkkkkkokkokkkookoookkkkokokkokokkkookkokkokkkookkkoooookokookookkkooookkkookookookokookokkkookookkkkkookkokookookooooooookokkkokookkkkookokokkkkooooookkkkkooookkokkokkokkkkokokookkkkookkokkokokokokokkookkkooooookkkokkkooo...
output:
125951
result:
ok single line: '125951'
Test #31:
score: 0
Accepted
time: 2ms
memory: 7752kb
input:
554 590 oookokokokkookookokokkooookokkkkokkkkkkkkkoookokokookkooookkkokkkkokkooookooooooookooookokoookkkooookkookkkookkkokkkkookkokkkkookkoooookooookkkkoooookookookkkkookkoookkkoookokookkkokkokkooooooookkkkoookokkkookoookkookoookkkkkokkokokkookkkoookkkoookokkkkkokkkkkookookokookkkookkkoookokokkkkkko...
output:
36325
result:
ok single line: '36325'
Test #32:
score: 0
Accepted
time: 2ms
memory: 7756kb
input:
501 244 okookkoookkoooooooookkkookokoookkkookokkkkokkoooooooookooookokookooookkookooookkkokokokkkokkoookoookkokkkoooooooookokoookokkkookokookkooookokkooooooookkkooookkkookkkkokkkoookoookkookkkokookoookkkkokokkkkkkoookkkkkokkooooookooookokokkkokokkkooookkookkkokkookkokkkkookkookkokkokoookokkoookkokko...
output:
52099
result:
ok single line: '52099'
Test #33:
score: 0
Accepted
time: 2ms
memory: 7736kb
input:
169 292 kookkoookkoooooookkkokkkooookkokkokkkookookkookkokokkokkkkkokokkokokokookookkookooookkoookkkkookokokkookkkookokkoookokooooookokoooookokkkkooooookokkooookokkkookokkokkkookkkokkkokokkoookkookkkokkookookokkkookkkkkkkoookkkkkoooooookkoookkookkkkokookooookkkkooookkkookookokkkkkkkoookokoookkokokok...
output:
120570
result:
ok single line: '120570'
Test #34:
score: 0
Accepted
time: 1ms
memory: 8008kb
input:
357 690 kkkkoookokkkookooooookokookkokkookokkkkkoookookkkooookkkokkkooookokkkookkkkkoookkokookooookookokookkkkkkkokokooookkkkkkokokoookkkkkkookokkkokokkkkokoookokkokkookoookokooookkkkkokkokookkkkkookkkkoookkkkokkkkokkkkkookkkkokkookookkkkkooooooookookokokkkkokkokokkkkkkookkokkkkookkkkkkkkkkkookokoko...
output:
217221
result:
ok single line: '217221'
Test #35:
score: 0
Accepted
time: 1ms
memory: 5788kb
input:
266 1115 kokokkookkkkkookkokkookoookoooookokoooookokkokkokkkokookkkkkkkkookkkkkokokooookkokookookkkoooookkooookkoookkkkkkokokooookkoookokookkkkkoookokkkkkkookkokkokkkoookokooooookkkokkkkokokkookoooooookooooookokokkokkkkookkkkoookoookkkkkkkoooooookokookookokokokokkookoooookokoookkokokookookkkokokokok...
output:
284665
result:
ok single line: '284665'
Test #36:
score: 0
Accepted
time: 2ms
memory: 6020kb
input:
1587 1962 kkkkooookkokkoookkokkkkkkooookooookokokkkkkkooookkokokkkkkkokokokokkokokkkkkokkookoooookookkkkkkoookokkkokoookokkkookokkokkkooooookokkokkokkkokoookkkoookookkokookkkoooookkokoookokkookkokoooooookkokkkooookkkkookokkokokkoooookkkkkoooooookokkokoookokokkookookokkkookooookokkokoookkkokkkkkkookk...
output:
215087
result:
ok single line: '215087'
Test #37:
score: 0
Accepted
time: 2ms
memory: 5832kb
input:
4299 2968 oookkookkkkokookkkokookkkkooookookkkookkkookkkoookokooooookokokoookkkoooooookkokokookokokokookookokkkokkkkookkooookokkkkokokkkkokkoookokoooookkokkokkkkkokoookkokoookokoookkokkooookkokkkkokkkookkoookookkokookkkkkkkoookokkoookokkokooookkokkkkkokooookokookookkkkkkkkokokokokokkkkkkookkkkoookok...
output:
7912001
result:
ok single line: '7912001'
Test #38:
score: 0
Accepted
time: 15ms
memory: 5952kb
input:
732 255 kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk...
output:
4979
result:
ok single line: '4979'
Test #39:
score: 0
Accepted
time: 188ms
memory: 8076kb
input:
1905 815 kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk...
output:
1986
result:
ok single line: '1986'
Test #40:
score: 0
Accepted
time: 597ms
memory: 8460kb
input:
156 1659 ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...
output:
2
result:
ok single line: '2'
Test #41:
score: 0
Accepted
time: 1147ms
memory: 8452kb
input:
217 3156 ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooookoooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...
output:
0
result:
ok single line: '0'
Test #42:
score: -100
Time Limit Exceeded
input:
2112 507 kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk...