252912026-02-19 01:43:47999DNScpp17Elfogadva 40/4048ms5368 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    string s;cin>>s;
    int n=s.size();
    vector<int> v(n);
    string S="ACGT";
    int ans=1;
    for(char c:S){
        for(int i = 0;i<n;i++){
            if(s[i]==c)v[i]=1;
            else v[i]=-1;
        }
        vector<int> pref(n),mx(n);
        pref[0]=v[0];
        mx[0]=pref[0];
        for(int i = 1;i<n;i++){
            pref[i]=pref[i-1]+v[i];
            mx[i]=min(pref[i],mx[i-1]);
        }
        /*for(int i : mx)cout<<i<<' ';
        cout<<endl;
        for(int i : pref)cout<<i<<' ';
        cout<<endl;*/
        for(int i = 1;i<n;i++){
            int x=pref[i];
            if(x>=0){
                ans=max(ans,i+1);
                continue;
            }
            if(mx[i-1]>x)continue;
            int lo=-1,hi=i,mi=0;
            while(lo<hi-1){
                mi=(lo+hi+1)/2;
                if(mx[mi]<=x)hi=mi;
                else lo=mi;
            }
            //cout<<hi<<' '<<i<<endl;
            ans=max(ans,i-hi);
        }//cout<<endl;
    }cout<<ans;
}

/*
sum=pref[i]-pref[j-1]>=0
pref[i]>=pref[j-1]
kell
*/
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/01ms316 KiB
2Elfogadva0/048ms5316 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms336 KiB
7Elfogadva2/21ms548 KiB
8Elfogadva4/48ms1704 KiB
9Elfogadva4/414ms2496 KiB
10Elfogadva4/419ms2932 KiB
11Elfogadva4/427ms3564 KiB
12Elfogadva4/429ms4036 KiB
13Elfogadva5/535ms4804 KiB
14Elfogadva5/539ms5368 KiB