1502021-02-02 18:16:12kidesoDNScpp11Time limit exceeded 14/40400ms6088 KiB
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

//ifstream cin("muti.in");
//ofstream cout("muti.out");

struct adat
{
    int sz[5] = { 0,0,0,0,0 };
};

string s;
int k, maxi, i, N, maxi1, p;
bool jo;
map <char, int> kar;

int main()
{
    cin >> s;
    N = s.size();
    vector <adat> x(N + 1);
    
    kar['A'] = 1;
    kar['C'] = 2;
    kar['G'] = 3;
    kar['T'] = 4;

    maxi = 1;

    for (i = 1; i <= N; ++i)
    {
        k = kar[s[i - 1]];

        for (int j = 1; j <= 4; ++j)
        {
            if (j == k) x[i].sz[j] = x[i - 1].sz[j] + 1;
            else x[i].sz[j] = x[i - 1].sz[j];

            x[i].sz[0] = max(x[i].sz[0], x[i].sz[j]);
        }
    }

    for (i = 2; i <= N; ++i)
    {
        maxi1 = x[i].sz[0];

        k = max(1, i - 2 * maxi1 + 1);
        jo = false;

        while (!jo)
        {
            for (int j = 1; j <= 4; ++j)
            {
                p = x[i].sz[j] - x[k - 1].sz[j];
                if (2 * p >= i - k + 1)
                {
                    jo = true;
                    break;
                }
            }

            ++k;
        }

        --k;
        maxi = max(maxi, i - k + 1);
    }
        
    cout << maxi;
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base14/40
1Accepted0/02ms1740 KiB
2Time limit exceeded0/0395ms5320 KiB
3Accepted2/21ms2020 KiB
4Accepted2/21ms2036 KiB
5Accepted2/21ms2048 KiB
6Accepted2/21ms2052 KiB
7Accepted2/23ms2076 KiB
8Accepted4/4135ms3944 KiB
9Time limit exceeded0/4317ms5552 KiB
10Time limit exceeded0/4395ms3508 KiB
11Time limit exceeded0/4393ms4268 KiB
12Time limit exceeded0/4381ms4844 KiB
13Time limit exceeded0/5342ms5500 KiB
14Time limit exceeded0/5400ms6088 KiB