14432022-10-10 13:59:22AbbenceDNScpp17Accepted 40/40243ms24484 KiB
#include <bits/stdc++.h>

using namespace std;

/*
mutans DNS OKTV

   C  T  G  G  T  A  C  C  C
C  1  0 -1 -2 -3 -4 -3 -2 -1
...
*/

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie();

    string dns;
    cin >> dns;
    int n = dns.length();

    int maxTavolsag = 0;
    char gen[] = {'C','T','G','A'};
    for(auto g: gen){
        int tav = 0; // pillanatnyi genre szamitott max tavolsag
        int tomb[n+1] = {0}; // 0. elem sgd
        for(int i=1; i<n+1; i++){
            if(dns.at(i-1) == g){
                tomb[i] = tomb[i-1] + 1;
            }
            else{
                tomb[i] = tomb[i-1] - 1;
            }
        }
        if(tomb[n] >= 0){
            tav = n; // tobb, mint a fele ugyanolyan -> az egesz mutans
        }
        else{
            map<int,int> legelso; // legelso i szám a segédtömbben (tav = legutolsó - legelső)
            for(int i=1; i<n+1; i++){
                if(tomb[i] >= 0){ // [0;i] jó
                    tav = i;
                }
                else{
                    if(legelso.find(tomb[i]) == legelso.end()){ // ha még nincs bent <=> legelső
                        legelso[tomb[i]] = i;
                    }
                    else if(i - legelso[tomb[i]] > tav){
                        tav = i - legelso[tomb[i]];
                    }
                }
            }
//            cerr << endl << g << endl;
//            for(auto l: legelso){
//            cerr << l.first << " " << l.second << endl;
//            }
        }

//        for(int i=0; i<n+1; i++){
//            cerr << tomb[i] << " ";
//        }
//        cerr << endl;
//        cerr << "tav: " << tav << endl;


        if(tav > maxTavolsag) maxTavolsag = tav;
    }

    cout << maxTavolsag << endl;

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base40/40
1Accepted0/03ms1960 KiB
2Accepted0/0243ms15832 KiB
3Accepted2/22ms2228 KiB
4Accepted2/22ms2452 KiB
5Accepted2/22ms2508 KiB
6Accepted2/22ms2672 KiB
7Accepted2/23ms3020 KiB
8Accepted4/443ms6652 KiB
9Accepted4/475ms8704 KiB
10Accepted4/497ms9804 KiB
11Accepted4/4135ms12112 KiB
12Accepted4/4128ms18976 KiB
13Accepted5/5158ms22284 KiB
14Accepted5/5178ms24484 KiB