QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#137506#2354. OokRd_rainydays#WA 2ms7848kbC++141.7kb2023-08-10 13:36:292023-08-10 13:36:43

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 13:36:43]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7848kb
  • [2023-08-10 13:36:29]
  • 提交

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

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 7724kb

input:

2 1
ookookook
koo

output:

10

result:

ok single line: '10'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5720kb

input:

1 3
koooooook
?

output:

13

result:

ok single line: '13'

Test #3:

score: 0
Accepted
time: 2ms
memory: 7696kb

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: 5908kb

input:

1 0
ookko
k??ko

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 2ms
memory: 7836kb

input:

5 8
koookokkok
oo

output:

32

result:

ok single line: '32'

Test #7:

score: 0
Accepted
time: 2ms
memory: 7844kb

input:

12 13
kkokoookokkooko
?ooo??ook?k?

output:

18

result:

ok single line: '18'

Test #8:

score: 0
Accepted
time: 2ms
memory: 7744kb

input:

8 9
kkkkkkkkokkkokkokkok
o????k???oo?o

output:

28

result:

ok single line: '28'

Test #9:

score: 0
Accepted
time: 0ms
memory: 5912kb

input:

2 11
kkkoooooooookkookookokooo
kkkokkkok?ok??okok

output:

1

result:

ok single line: '1'

Test #10:

score: -100
Wrong Answer
time: 0ms
memory: 7808kb

input:

0 14
kkookookkkokkkokkoooookokkkokk
oooo?kooo?k

output:

15

result:

wrong answer 1st lines differ - expected: '22', found: '15'