/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 556.0 KiB
#2 Wrong Answer 1ms 316.0 KiB
#3 Wrong Answer 21ms 552.0 KiB

Code

#include<bits/stdc++.h>
using namespace std; 
char nl = '\n';
using i64 = long long;

void solve(int t) {
    // cout << "test #" << t << nl;
    i64 n, k; cin >> n >> k;
    string str; cin >> str;
    vector<i64> cnt1(n + 1), cnt2(n + 1);
    i64 tot = 0, already = 0;
    i64 x = -1;
    i64 q = 0;
    for (auto& a : str) {
        tot += a == 'B';
    }
    for (int i = 0; i < n; i++) {
        if (str[i] == 'B') tot--;
        if (str[i] == '?') {
            q++;
            x++;
            already += tot;
            cnt1[x] = already;
        }
    }
    k = min(k, q);
    reverse(str.begin(), str.end());
    tot = 0; already = 0, x = -1;
    for (auto& a : str) {
        tot += a == 'A';
    }
    for (int i = 0; i < n; i++) {
        if (str[i] == 'A') tot--;
        if (str[i] == '?') {
            x++;
            already += tot;
            cnt2[x] = already;
        }
    }
    reverse(str.begin(), str.end());
    i64 ans = 0;
    for (i64 i = 0; i <= k; i++) {
        ans = max(ans, i * (k - i) + cnt1[i] + cnt2[k - i]);
        // cout << cnt1[i] << " " << cnt2[k - i] << nl;
    }
    tot = 0, already = 0, x = 0;
    for (int i = 0; i < n; i++) {
        tot += str[i] == 'B';
    }
    for (int i = 0; i < n; i++) {
        if (str[i] == 'A') {
            ans += tot;
        } else if (str[i] == 'B') {
            tot -= 1;
        }
    }
    cout << ans << nl;
} 

int main() {
    int tt = 1;
    cin >> tt;
    for(int t = 1; t <= tt; t++) solve(t);
}

Information

Submit By
Type
Submission
Problem
P1110 Subsequence of AB
Contest
Brain Booster #7
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-05 15:36:08
Judged At
2024-11-05 15:36:08
Judged By
Score
1
Total Time
21ms
Peak Memory
556.0 KiB