207082026-01-08 18:06:04algoproDNScpp17Elfogadva 40/40174ms14860 KiB
// UUID: 161c27ea-3445-45b0-829b-d31a25de422f
#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);
    unordered_map <int,int> m;
    vector <array <int,2>> 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 INF = 2e9;
    t.push_back({INF , 0});
    int T = t.size();
    sort(t.rbegin(),t.rend());
    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++){
        if(p[i] >= 0){
            ans = max(i, ans);
            continue;
        }
        int pos = 2e9;
        int l = 0, r = T-1;
        while(l <= r){
            int mid = (l+r)/2;
            if(t[mid][0] <= p[i]){
                pos = min(pos, mid);
                r = mid - 1;
            }
            else l = mid + 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/01ms504 KiB
2Elfogadva0/0174ms9488 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms508 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms316 KiB
7Elfogadva2/21ms316 KiB
8Elfogadva4/441ms2976 KiB
9Elfogadva4/468ms4416 KiB
10Elfogadva4/479ms4716 KiB
11Elfogadva4/4104ms6432 KiB
12Elfogadva4/4112ms10988 KiB
13Elfogadva5/5148ms13872 KiB
14Elfogadva5/5153ms14860 KiB