239242026-01-31 20:26:36TakacsAndrasDNScpp17Elfogadva 40/40149ms8500 KiB
#include <bits/stdc++.h>
using namespace std;
int st[2000000];
const int c = 2e5, n = 2*c+5;
int qr(int r) {
    int l = n;
    r += n;
    int mn = st[r];
    while (l <= r && (l || r)) {
        if (l % 2 == 1) mn = min(mn,st[l++]);
        if (r % 2 == 0) mn = min(mn,st[r--]);
        l /= 2;
        r /= 2;
    }
    return mn;
}
void upd(int i, int x) {
    i += n;
    st[i] = min(st[i],x);
    i /= 2;
    while (i) {
        st[i] = min(st[i*2],st[i*2+1]);
        i /= 2;
    }
}
int main() {
    string s; cin >> s;
    vector<char> ps = {'A','C','G','T'};
    int out = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 2e6; j++) st[j] = 2e5;
        upd(c,-1);
        int cnt = 0, mx = 0;
        for (int j = 0; j < s.size(); j++) {
            if (s[j] == ps[i]) cnt++;
            else cnt--;
            int ind = qr(cnt+c);
            mx = max(mx,j-ind);
            upd(cnt+c,j);
        }
        out = max(out,mx);
    }
    cout << out << '\n';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/08ms7988 KiB
2Elfogadva0/0149ms8388 KiB
3Elfogadva2/28ms7992 KiB
4Elfogadva2/29ms7988 KiB
5Elfogadva2/28ms7988 KiB
6Elfogadva2/29ms8208 KiB
7Elfogadva2/28ms8236 KiB
8Elfogadva4/446ms8500 KiB
9Elfogadva4/464ms8300 KiB
10Elfogadva4/481ms8272 KiB
11Elfogadva4/4101ms8388 KiB
12Elfogadva4/4101ms8380 KiB
13Elfogadva5/5119ms8388 KiB
14Elfogadva5/5133ms8392 KiB