19692022-12-12 17:40:08sztomiDNScpp17Wrong answer 34/4086ms10908 KiB
#include <bits/stdc++.h>

using namespace std;

int main()
{
    string s;
    cin >> s;

    map<char, vector<int>> db;
    string betuk = "ACGT";
    for(auto x : betuk){
        db[x] = vector<int>(s.size()+1, 0);
    }
    for(int i = 1; i <= s.size(); i++){
        for(auto x : betuk){
            db[x][i] = db[x][i-1];
        }
        db[s[i-1]][i]++;
    }

    int mo = 0;
    int l = 0;
    int r = s.size();
    int mid;
    while(l <= r){
        mid = (l+r) / 2;
        bool lehet = false;
        for(int i = 1; i <= s.size() - mid + 1; i++){
            int legtobb = 0;
            for(auto x : betuk){
                legtobb = max(legtobb, db[x][i+mid-1] - db[x][i-1]);
            }
            if(legtobb*2 >= mid){
                lehet = true;
                break;
            }
        }
        if(lehet){
            mo = mid;
            l = mid+1;
        }
        else{
            r = mid-1;
        }
    }
    cout << mo << "\n";
}
SubtaskSumTestVerdictTimeMemory
base34/40
1Accepted0/03ms1812 KiB
2Wrong answer0/086ms8904 KiB
3Wrong answer0/22ms2260 KiB
4Accepted2/22ms2452 KiB
5Wrong answer0/22ms2528 KiB
6Accepted2/22ms2668 KiB
7Wrong answer0/22ms2812 KiB
8Accepted4/46ms4736 KiB
9Accepted4/48ms6108 KiB
10Accepted4/425ms6756 KiB
11Accepted4/424ms7916 KiB
12Accepted4/452ms9028 KiB
13Accepted5/561ms10132 KiB
14Accepted5/568ms10908 KiB