1512021-02-02 18:20:07kidesoDNScpp11Time limit exceeded 18/40333ms5236 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+=2;
        }

        k -= 2;
        maxi = max(maxi, i - k + 1);
    }
        
    cout << maxi;
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base18/40
1Accepted0/02ms1744 KiB
2Time limit exceeded0/0319ms5128 KiB
3Accepted2/21ms1720 KiB
4Accepted2/22ms1768 KiB
5Accepted2/21ms1828 KiB
6Accepted2/21ms1840 KiB
7Accepted2/23ms1848 KiB
8Accepted4/475ms3716 KiB
9Accepted4/4157ms5236 KiB
10Time limit exceeded0/4319ms3084 KiB
11Time limit exceeded0/4333ms3760 KiB
12Time limit exceeded0/4330ms4080 KiB
13Time limit exceeded0/5326ms4784 KiB
14Time limit exceeded0/5328ms5128 KiB