206972026-01-08 17:56:32algoproDNScpp17Time limit exceeded 38/40307ms16832 KiB
// UUID: 26a6eaf0-9680-400e-a603-767d21581448
#include <bits/stdc++.h>
using namespace std;
string dns;
int n;
int solve(char c)
{
    int ans = 0;
    vector <int> v(n+1), p(n+1);
    map <int,int> m;
    vector <array <int,3>> t;
    for(int i = 1; i <= n; i++){
        if(dns[i] == c) v[i]++;
        else v[i]--;
    }
    for(int i = 1; i <= n; i++){
       p[i] = p[i-1] + v[i];
       if(m[p[i]] == 0) m[p[i]] = i;
    }

    for(auto [key, val] : m){
        t.push_back({key,val});
    }
    int T = t.size();
    reverse(t.begin(),t.end());
    vector <int> s(T,2e9);
    int mini = 2e9;
    for(int i = T-1; i > 0; i--){
        mini = min(mini, t[i][1]);
        s[i] = mini;
    }
    for(int i = 1; i <= n; i++){
        int pos = 2e9;
        int l = 0, r = T-1;
        while(l <= r){
            int m = (l+r)/2;
            if(t[m][0] <= p[i]){
                pos = min(pos, m);
                r = m - 1;
            }
            else l = m + 1;
        }
        if(pos == 2e9) continue;
        ans = max(ans, i-s[pos]);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> dns;
    n = dns.size();
    dns = ' ' + dns;
    int a = solve('A'), c = solve('C'), g = solve('G'), t = solve('T');
    cout << max(a,max(c,max(g,t)));

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base38/40
1Accepted0/01ms500 KiB
2Time limit exceeded0/0307ms11108 KiB
3Accepted2/21ms316 KiB
4Accepted2/21ms316 KiB
5Accepted2/21ms316 KiB
6Wrong answer0/21ms316 KiB
7Accepted2/21ms316 KiB
8Accepted4/461ms3568 KiB
9Accepted4/4100ms5000 KiB
10Accepted4/4128ms5516 KiB
11Accepted4/4171ms7832 KiB
12Accepted4/4184ms13528 KiB
13Accepted5/5234ms15416 KiB
14Accepted5/5250ms16832 KiB