912021-01-10 22:52:33Babják PéterDNScpp11Accepted 40/408ms8176 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
   	string s;cin>>s;
   	int sz=s.size();
   	char t[4]={'A','C','T','G'};
   	int mx=0;
	for(char c:t)
	{
		int tm[sz];	
		int first[400040];
		for(int i=0;i<400040;i++)
		{
			first[i]=-2;
		}
		tm[0]=200002+((s[0]==c) ? 1 : -1);
		first[tm[0]]=0;
		first[200002]=-1;
		for(int i=1;i<sz;i++)
		{
			tm[i]=tm[i-1]+((s[i]==c)? 1 : -1);//tm[i] az elsõ i karakter között levõ db(c)-db(másik3ch)
			if(first[tm[i]]!=-2)//ez a részösszeg már volt egyszer azaz valamelyik állapotba "visszatértünk"
			{
				mx=max(mx,i-first[tm[i]]);//a 2 közti szakaszon annyit csökkent mint amennyit nõtt azaz a szakasznak legalább fele c volt.
			}
			else
			{
				first[tm[i]]=i;
			}
		}
		if(tm[sz-1]>=200002)
		{
			mx=sz;
		}
	}
	cout<<mx<<endl;
   	return 0;
}
SubtaskSumTestVerdictTimeMemory
base40/40
1Accepted0/04ms4848 KiB
2Accepted0/08ms7268 KiB
3Accepted2/23ms5136 KiB
4Accepted2/23ms5136 KiB
5Accepted2/24ms5144 KiB
6Accepted2/23ms5144 KiB
7Accepted2/23ms5160 KiB
8Accepted4/44ms5844 KiB
9Accepted4/44ms6296 KiB
10Accepted4/44ms6512 KiB
11Accepted4/46ms6852 KiB
12Accepted4/46ms7204 KiB
13Accepted5/56ms7668 KiB
14Accepted5/57ms8176 KiB