QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#137575#2354. OokRd_rainydays#TL 1147ms8460kbC++141.7kb2023-08-10 13:59:502023-08-10 14:05:12

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-10 14:05:12]
  • 评测
  • 测评结果:TL
  • 用时:1147ms
  • 内存:8460kb
  • [2023-08-10 13:59:50]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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...

output:


result: