/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 436.0 KiB
#2 Accepted 2ms 512.0 KiB
#3 Accepted 13ms 576.0 KiB
#4 Accepted 6ms 560.0 KiB
#5 Accepted 6ms 492.0 KiB
#6 Accepted 6ms 644.0 KiB
#7 Accepted 5ms 796.0 KiB
#8 Accepted 6ms 496.0 KiB
#9 Accepted 8ms 544.0 KiB
#10 Accepted 7ms 624.0 KiB
#11 Accepted 5ms 612.0 KiB
#12 Accepted 4ms 484.0 KiB
#13 Accepted 4ms 580.0 KiB
#14 Accepted 3ms 588.0 KiB
#15 Accepted 8ms 968.0 KiB
#16 Accepted 4ms 1.043 MiB
#17 Accepted 6ms 1.207 MiB
#18 Accepted 9ms 1.969 MiB
#19 Accepted 8ms 4.074 MiB
#20 Accepted 6ms 1.301 MiB
#21 Accepted 5ms 976.0 KiB

Code

#include<bits/stdc++.h>
using namespace std;
const long long M=2e5+10,MOD=1000000007;
typedef long long ll;
#define debug(x) cout<<x<<endl

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
       int n,k;
       cin>>n>>k;
       string s;
       cin>>s;
       ll ans=0;
       int temp=k;
       string p=s;
       ll cntA=0;
       for(int i=0;i<n;i++)cntA+=(s[i]=='A');
       vector<ll>occA;
       for(int i=n-1;i>=0&&temp>0;i--){
          cntA-=(s[i]=='A');
          if(s[i]=='?'){
            p[i]='B';
            temp--;
            occA.push_back(cntA);
          }
       }
       ll cntB=0;
       for(int i=0;i<n;i++)cntB+=(p[i]=='B');
       ll tempB=cntB;
       for(int  i=0;i<n;i++){
        tempB-=(p[i]=='B');
        if(s[i]=='A'){
            ans+=tempB;
        }
       }
       ll answer=ans;
       int pos=(int)occA.size()-1;
      // debug(ans);
       ll newA=0;
       for(int i=0;i<n&&pos>=0;i++){
          cntB-=(s[i]=='B');
          if(s[i]=='?'){
            ans-=occA[pos];
            cntB--;
            pos--;
            ans+=cntB;
            ans-=newA;
            newA++;
          }
          answer=max(answer,ans);
       }
       cout<<answer<<"\n";
    }
    

    
    return 0;
 
}

Information

Submit By
Type
Submission
Problem
P1110 Subsequence of AB
Language
C++17 (G++ 13.2.0)
Submit At
2024-10-10 10:01:19
Judged At
2024-11-11 02:38:05
Judged By
Score
100
Total Time
13ms
Peak Memory
4.074 MiB